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

Commitbaf55b4

Browse files
Update
1 parent41656d1 commitbaf55b4

6 files changed

+294
-30
lines changed

‎README.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -118,6 +118,9 @@
118118
*[二叉树：搜索树的最小绝对差](https://mp.weixin.qq.com/s/Hwzml6698uP3qQCC1ctUQQ)
119119
*[二叉树：我的众数是多少？](https://mp.weixin.qq.com/s/KSAr6OVQIMC-uZ8MEAnGHg)
120120
*[二叉树：公共祖先问题](https://mp.weixin.qq.com/s/n6Rk3nc_X3TSkhXHrVmBTQ)
121+
*[本周小结！（二叉树系列四）](https://mp.weixin.qq.com/s/CbdtOTP0N-HIP7DR203tSg)
122+
*[二叉树：搜索树的公共祖先问题](https://mp.weixin.qq.com/s/Ja9dVw2QhBcg_vV-1fkiCg)
123+
*[二叉树：搜索树中的插入操作](https://mp.weixin.qq.com/s/lwKkLQcfbCNX2W-5SOeZEA)
121124

122125

123126

@@ -262,6 +265,7 @@
262265
|[0077.组合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0077.组合.md)|回溯|中等|**回溯**|
263266
|[0078.子集](https://github.com/youngyangyang04/leetcode/blob/master/problems/0078.子集.md)|回溯/数组|中等|**回溯**|
264267
|[0083.删除排序链表中的重复元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0083.删除排序链表中的重复元素.md)|链表|简单|**模拟**|
268+
|[0084.柱状图中最大的矩形](https://github.com/youngyangyang04/leetcode/blob/master/problems/0084.柱状图中最大的矩形.md)|数组|困难|**单调栈**|
265269
|[0090.子集II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0090.子集II.md)|回溯/数组|中等|**回溯**|
266270
|[0093.复原IP地址](https://github.com/youngyangyang04/leetcode/blob/master/problems/0093.复原IP地址)|回溯|中等|**回溯**|
267271
|[0094.二叉树的中序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0094.二叉树的中序遍历.md)|树|中等|**递归****迭代/栈**|

‎problems/0084.柱状图中最大的矩形.md

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,3 +29,77 @@ public:
2929
```
3030

3131
如上代码并不能通过leetcode，超时了，因为时间复杂度是O(n^2)。
32+
33+
##思考一下动态规划
34+
35+
##单调栈
36+
37+
单调栈的思路还是不容易理解的，
38+
39+
想清楚从大到小，还是从小到大，
40+
41+
本题是从栈底到栈头 从小到大，和 接雨水正好反过来。
42+
43+
44+
45+
```
46+
class Solution {
47+
public:
48+
int largestRectangleArea(vector<int>& heights) {
49+
stack<int> st;
50+
heights.insert(heights.begin(), 0); // 数组头部加入元素0
51+
heights.push_back(0); // 数组尾部加入元素0
52+
st.push(0);
53+
int result = 0;
54+
// 第一个元素已经入栈，从下表1开始
55+
for (int i = 1; i < heights.size(); i++) {
56+
// 注意heights[i] 是和heights[st.top()] 比较 ，st.top()是下表
57+
if (heights[i] > heights[st.top()]) {
58+
st.push(i);
59+
} else if (heights[i] == heights[st.top()]) {
60+
st.pop(); // 这个可以加，可以不加，效果一样，思路不同
61+
st.push(i);
62+
} else {
63+
while (heights[i] < heights[st.top()]) { // 注意是while
64+
int mid = st.top();
65+
st.pop();
66+
int left = st.top();
67+
int right = i;
68+
int w = right - left - 1;
69+
int h = heights[mid];
70+
result = max(result, w * h);
71+
}
72+
st.push(i);
73+
}
74+
}
75+
return result;
76+
}
77+
};
78+
79+
```
80+
81+
代码精简之后：
82+
83+
```
84+
class Solution {
85+
public:
86+
int largestRectangleArea(vector<int>& heights) {
87+
stack<int> st;
88+
heights.insert(heights.begin(), 0); // 数组头部加入元素0
89+
heights.push_back(0); // 数组尾部加入元素0
90+
st.push(0);
91+
int result = 0;
92+
for (int i = 1; i < heights.size(); i++) {
93+
while (heights[i] < heights[st.top()]) {
94+
int mid = st.top();
95+
st.pop();
96+
int w = i - st.top() - 1;
97+
int h = heights[mid];
98+
result = max(result, w * h);
99+
}
100+
st.push(i);
101+
}
102+
return result;
103+
}
104+
};
105+
```

‎problems/0143.重排链表.md

Lines changed: 9 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -26,8 +26,8 @@ public:
2626
}
2727
cur = head;
2828
int i = 1;
29-
int j = vec.size() - 1;
30-
int count = 0; // 计数，用来取前面，取后面
29+
int j = vec.size() - 1; // i j为之前前后的双指针
30+
int count = 0; // 计数，偶数去后面，奇数取前面
3131
while (i <= j) {
3232
if (count % 2 == 0) {
3333
cur->next = vec[j];
@@ -39,7 +39,7 @@ public:
3939
cur = cur->next;
4040
count++;
4141
}
42-
if (vec.size() % 2 == 0) {
42+
if (vec.size() % 2 == 0) { // 如果是偶数，还要多处理中间的一个
4343
cur->next = vec[i];
4444
cur = cur->next;
4545
}
@@ -54,7 +54,7 @@ public:
5454
```
5555
class Solution {
5656
public:
57-
void reorderList(ListNode* head) {
57+
void reorderList(ListNode* head) {
5858
deque<ListNode*> que;
5959
ListNode* cur = head;
6060
if (cur == nullptr) return;
@@ -65,7 +65,7 @@ public:
6565
}
6666
6767
cur = head;
68-
int count = 0;
68+
int count = 0; // 计数，偶数去后面，奇数取前面
6969
ListNode* node;
7070
while(que.size()) {
7171
if (count % 2 == 0) {
@@ -79,7 +79,7 @@ public:
7979
cur->next = node;
8080
cur = cur->next;
8181
}
82-
cur->next = nullptr;
82+
cur->next = nullptr; // 注意结尾
8383
}
8484
};
8585
```
@@ -99,6 +99,7 @@ public:
9999
```
100100
class Solution {
101101
private:
102+
// 反转链表
102103
ListNode* reverseList(ListNode* head) {
103104
ListNode* temp; // 保存cur的下一个节点
104105
ListNode* cur = head;
@@ -137,7 +138,7 @@ public:
137138
ListNode* cur2 = head2;
138139
ListNode* cur = head;
139140
cur1 = cur1->next;
140-
int count = 0;
141+
int count = 0; // 偶数取head2的元素，奇数取head1的元素
141142
while (cur1 && cur2) {
142143
if (count % 2 == 0) {
143144
cur->next = cur2;
@@ -149,7 +150,7 @@ public:
149150
count++;
150151
cur = cur->next;
151152
}
152-
if (cur2 != nullptr) {
153+
if (cur2 != nullptr) { // 处理结尾
153154
cur->next = cur2;
154155
}
155156
if (cur1 != nullptr) {

0 commit comments

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