Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitaac59ff

Browse files
author
luzhipeng
committed
1 parent83fc7a6 commitaac59ff

14 files changed

+170
-65
lines changed

‎152.maximum-product-subarray.js

Lines changed: 0 additions & 61 deletions
This file was deleted.

‎README.md

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
1414

1515
- 第四部分是计划， 这里会记录将来要加入到以上三个部分内容
1616

17-
>只有熟练掌握基础的数据结构与算法，才能对复杂问题迎刃有余
17+
>只有熟练掌握基础的数据结构与算法，才能对复杂问题迎刃有余。
1818
1919
##食用指南
2020

@@ -115,6 +115,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
115115
-[139.word-break](./problems/139.word-breakmd)
116116
-[144.binary-tree-preorder-traversal](./problems/144.binary-tree-preorder-traversal.md)
117117
- 🖊[150.evaluate-reverse-polish-notation](./problems/150.evaluate-reverse-polish-notation.md)
118+
- 🆕[152.maximum-product-subarray](./problems/152.maximum-product-subarray.md)
118119
-[199.binary-tree-right-side-view](./problems/199.binary-tree-right-side-view.md)
119120
-[201.bitwise-and-of-numbers-range](./problems/201.bitwise-and-of-numbers-range.md)
120121
- 🆕[208.implement-trie-prefix-tree](./problems/208.implement-trie-prefix-tree.md)
@@ -132,6 +133,7 @@ leetcode 题解，记录自己的 leetcode 解题之路。
132133
-[900.rle-iterator](./problems/900.rle-iterator.md)
133134

134135
####困难难度
136+
- 🆕[23.merge-k-sorted-lists](./problems/23.merge-k-sorted-lists.md)
135137
- 🆕[42.trapping-rain-water](./problems/42.trapping-rain-water.md)
136138
- 🆕[128.longest-consecutive-sequence](./problems/128.longest-consecutive-sequence.md)
137139
-[145.binary-tree-postorder-traversal](./problems/145.binary-tree-postorder-traversal.md)
30.3 KB
Loading
92.5 KB
Loading
Loading
File renamed without changes.
File renamed without changes.
File renamed without changes.
File renamed without changes.
Lines changed: 111 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,111 @@
1+
##题目地址
2+
3+
https://leetcode.com/problems/maximum-product-subarray/description/
4+
5+
##题目描述
6+
7+
```
8+
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
9+
10+
Example 1:
11+
12+
Input: [2,3,-2,4]
13+
Output: 6
14+
Explanation: [2,3] has the largest product 6.
15+
Example 2:
16+
17+
Input: [-2,0,-1]
18+
Output: 0
19+
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
20+
21+
```
22+
23+
##思路
24+
25+
>这道题目的通过率非常低
26+
27+
这道题目要我们求解连续的 n 个数中乘积最大的积是多少。这里提到了连续，笔者首先
28+
想到的就是滑动窗口，但是这里比较特殊，我们不能仅仅维护一个最大值，因此最小值（比如-20）乘以一个比较小的数（比如-10）
29+
可能就会很大。 因此这种思路并不方便。
30+
31+
首先来暴力求解,我们使用两层循环来枚举所有可能项，这种解法的时间复杂度是O(n^2), 代码如下：
32+
33+
```js
34+
varmaxProduct=function(nums) {
35+
let max= nums[0];
36+
let temp=null;
37+
for (let i=0; i<nums.length; i++) {
38+
temp= nums[i];
39+
max=Math.max(temp, max);
40+
for (let j= i+1; j<nums.length; j++) {
41+
temp*= nums[j];
42+
max=Math.max(temp, max);
43+
}
44+
}
45+
46+
return max;
47+
};
48+
```
49+
50+
因此我们需要同时记录乘积最大值和乘积最小值，然后比较元素和这两个的乘积，去不断更新最大值。
51+
52+
![152.maximum-product-subarray](../assets/problems/152.maximum-product-subarray.png)
53+
54+
这种思路的解法由于只需要遍历依次，其时间复杂度是O(n)，代码见下方代码区。
55+
##关键点
56+
57+
- 同时记录乘积最大值和乘积最小值
58+
59+
##代码
60+
61+
```js
62+
/*
63+
* @lc app=leetcode id=152 lang=javascript
64+
*
65+
* [152] Maximum Product Subarray
66+
*
67+
* https://leetcode.com/problems/maximum-product-subarray/description/
68+
*
69+
* algorithms
70+
* Medium (28.61%)
71+
* Total Accepted: 202.8K
72+
* Total Submissions: 700K
73+
* Testcase Example: '[2,3,-2,4]'
74+
*
75+
* Given an integer array nums, find the contiguous subarray within an array
76+
* (containing at least one number) which has the largest product.
77+
*
78+
* Example 1:
79+
*
80+
*
81+
* Input: [2,3,-2,4]
82+
* Output: 6
83+
* Explanation: [2,3] has the largest product 6.
84+
*
85+
*
86+
* Example 2:
87+
*
88+
*
89+
* Input: [-2,0,-1]
90+
* Output: 0
91+
* Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
92+
*
93+
*/
94+
/**
95+
*@param{number[]}nums
96+
*@return{number}
97+
*/
98+
varmaxProduct=function(nums) {
99+
let max= nums[0];
100+
let min= nums[0];
101+
let res= nums[0];
102+
103+
for (let i=1; i<nums.length; i++) {
104+
let tmp= min;
105+
min=Math.min(nums[i],Math.min(max* nums[i], min* nums[i]));// 取最小
106+
max=Math.max(nums[i],Math.max(max* nums[i], tmp* nums[i]));/// 取最大
107+
res=Math.max(res, max);
108+
}
109+
return res;
110+
};
111+
```

‎23.merge-k-sorted-lists.jsrenamed to‎problems/23.merge-k-sorted-lists.md

Lines changed: 51 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,47 @@
1+
##题目地址
2+
https://leetcode.com/problems/merge-k-sorted-lists/description
3+
4+
##题目描述
5+
6+
```
7+
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
8+
9+
Example:
10+
11+
Input:
12+
[
13+
1->4->5,
14+
1->3->4,
15+
2->6
16+
]
17+
Output: 1->1->2->3->4->4->5->6
18+
19+
```
20+
21+
##思路
22+
23+
这道题目是合并k个已排序的链表，号称leetcode目前`最难`的链表题。 和之前我们解决的[88.merge-sorted-array](./88.merge-sorted-array.md)很像。
24+
他们有两点区别：
25+
26+
1. 这道题的数据结构是链表，那道是数组。这个其实不复杂，毕竟都是线性的数据结构。
27+
28+
2. 这道题需要合并k个元素，那道则只需要合并两个。这个是两题的关键差别，也是这道题难度为`hard`的原因。
29+
30+
因此我们可以看出，这道题目是`88.merge-sorted-array`的进阶版本。其实思路也有点像，我们来具体分析下第二条。
31+
如果你熟悉合并排序的话，你会发现它就是`合并排序的一部分`。
32+
33+
具体我们可以来看一个动画
34+
35+
![23.merge-k-sorted-lists](../assets/problems/23.merge-k-sorted-lists.gif)
36+
37+
（动画来自https://zhuanlan.zhihu.com/p/61796021）
38+
##关键点解析
39+
40+
- 分治
41+
- 合并排序(merge sort)
42+
43+
##代码
44+
```js
145
/*
246
* @lc app=leetcode id=23 lang=javascript
347
*
@@ -30,8 +74,8 @@
3074
functionmergeTwoLists(l1,l2) {
3175
constdummyHead= {};
3276
let current= dummyHead;
33-
// 1 -> 3 -> 5
34-
// 2 -> 4 -> 6
77+
//l1:1 -> 3 -> 5
78+
//l2:2 -> 4 -> 6
3579
while (l1!==null&& l2!==null) {
3680
if (l1.val<l2.val) {
3781
current.next= l1;// 把小的添加到结果链表
@@ -83,3 +127,8 @@ var mergeKLists = function(lists) {
83127

84128
returnmergeTwoLists(mergeKLists(l1),mergeKLists(l2));
85129
};
130+
```
131+
132+
##相关题目
133+
134+
-[88.merge-sorted-array](./88.merge-sorted-array.md)

‎thinkings/binary-tree-traversal.md

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,8 +40,12 @@ BFS 的关键点在于如何记录每一层次是否遍历完成， 我们可以
4040

4141
其实从宏观上表现为：`自顶向下依次访问左侧链，然后自底向上依次访问右侧链`，
4242
如果从这个角度出发去写的话，算法就不一样了。从上向下我们可以直接递归访问即可，从下向上我们只需要借助栈也可以轻易做到。
43+
整个过程大概是这样：
44+
45+
![binary-tree-traversal-preorder](../assets/thinkings/binary-tree-traversal-preorder.png)
46+
4347
这种思路解题有点像我总结过的一个解题思路`backtrack` - 回溯法。这种思路有一个好处就是
44-
可以`统一三种遍历的思路`.
48+
可以`统一三种遍历的思路`. 这个很重要，如果不了解的朋友，希望能够记住这一点。
4549

4650
##中序遍历
4751

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp