LeetCode + 《剑指Offer II》刷题笔记。
栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> s;
int a,b,res;
for(string& temp:tokens){
if(isNumber(temp)){
s.push(atoi(temp.c_str()));
}else{
b=s.top();
s.pop();
a=s.top();
s.pop();
switch(temp[0]){
case '+':res=a+b;break;
case '-':res=a-b;break;
case '*':res=a*b;break;
case '/':res=a/b;break;
}
s.push(res);
}
}
return s.top();
}
bool isNumber(string& temp){
return !(temp=="+" || temp=="-" || temp=="*" || temp=="/");
}
};
|
735 Asteroid Collision
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
vector<int> stk;
for(int asteroid:asteroids){
while(!stk.empty() && stk.back()>0 && stk.back()<(-asteroid)){
stk.pop_back();
}
if(!stk.empty() && asteroid<0 && stk.back()==(-asteroid)){
stk.pop_back();
}else if(stk.empty() || asteroid>0 || stk.back()<0){
stk.push_back(asteroid);
}
}
return stk;
}
};
|
739 Daily Temperatures
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n=temperatures.size();
vector<int> res(n);
stack<int> stk;
for(int i=0;i<n;i++){
while(!stk.empty() && temperatures[i]>temperatures[stk.top()]){
int prev=stk.top();
stk.pop();
res[prev]=i-prev;
}
stk.push(i);
}
return res;
}
};
|
84 Largest Rectangle in Histogram
brute force
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n=heights.size();
int res=-1;
for(int i=0;i<n;i++){
int minHeight=heights[i];
for(int j=i;j<n;j++){
minHeight=min(minHeight,heights[j]);
res=max(res,(j-i+1)*minHeight);
}
}
return res;
}
};
|
运行结果：Time Limit Exceeded
divide and conquer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
return helper(heights,0,heights.size());
}
int helper(vector<int>& heights,int left,int right){
int res=0;
if(left==right) return res;
if(left+1==right) return heights[left];
int minIndex=left;;
for(int i=left+1;i<right;i++){
if(heights[i]<heights[minIndex]){
minIndex=i;
}
}
res=(right-left)*heights[minIndex];
int leftRes=helper(heights,0,minIndex);
int rightRes=helper(heights,minIndex+1,right);
res=max(res,leftRes);
res=max(res,rightRes);
return res;
}
};
|
-
假设输入数组的长度为n。如果每次都能将n根柱子分成两根柱子数量为n/2的子直方图，那么递归调用的深度为O（logn），整个分治法的时间复杂度是O（nlogn）。但如果直方图中柱子的高度是排序的（递增排序或递减排序），那么每次最矮的柱子都位于直方图的一侧，递归调用的深度就是O（n），此时分治法的时间复杂度也变成O（n^2）。
-
基于递归的分治法需要消耗内存来保存递归调用栈，空间复杂度取决于调用栈的深度，因此这种分治法的平均空间复杂度是O（logn），最坏情况下的空间复杂度是O（n）。
运行结果：Time Limit Exceeded
stack单调栈
这种解法的基本思想是确保保存在栈中的直方图的柱子的高度是递增排序的。假设从左到右逐一扫描数组中的每根柱子。如果当前柱子的高度大于位于栈顶的柱子的高度，那么将该柱子的下标入栈；否则，将位于栈顶的柱子的下标出栈，并且计算以位于栈顶的柱子为顶的最大矩形面积。
如果当前扫描到的柱子的高小于位于栈顶的柱子的高，那么将位于栈顶的柱子的下标出栈，并且计算以位于栈顶的柱子为顶的最大矩形面积。由于保存在栈中的柱子的高度是递增排序的，因此栈中位于栈顶前面的一根柱子一定比位于栈顶的柱子矮，于是很容易就能找到位于栈顶的柱子两侧比它矮的柱子。
参考视频：
LARGEST RECTANGLE IN HISTOGRAM - Leetcode 84 - Python
这道题也太不容易了，debug了好久😭。困难的时候就是在进步。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<pair<int,int>> stk;
int n=heights.size();
int start,index,height;
int area=0;
for(int i=0;i<n;i++){
start=i;
while(!stk.empty() && heights[i]<stk.top().second){
index=stk.top().first;
height=stk.top().second;
stk.pop();
area=max(area,height*(i-index));
start=index;
}
stk.push({start,heights[i]});
}
while(!stk.empty()){
index=stk.top().first;
height=stk.top().second;
stk.pop();
area=max(area,height*(n-index));
}
return area;
}
};
|
85 Maximal Rectangle
数组heights用来记录以某一行作为基线的直方图的每根柱子的高度。如果矩阵中某个格子的值为0，那么它所在的柱子的高度为0；如果矩阵中某个格子的值为1，那么它所在的柱子的高度是以上一行作为基线的直方图同一位置的柱子的高度加1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int maxArea=0;
if(matrix.size()==0 || matrix[0].size()==0) return maxArea;
vector<int> heights(matrix[0].size());
for(vector<char> row:matrix){
for(int i=0;i<row.size();i++){
if(row[i]=='0'){
heights[i]=0;
}else{
heights[i]++;
}
}
maxArea=max(maxArea,largestRectangleArea(heights));
}
return maxArea;
}
int largestRectangleArea(vector<int>& heights){
int maxArea=0;
int n=heights.size();
//key:index value:height
stack<pair<int,int>> stk;
int index,start,height;
for(int i=0;i<n;i++){
start=i;
while(!stk.empty() && heights[i]<stk.top().second){
index=stk.top().first;
height=stk.top().second;
stk.pop();
maxArea=max(maxArea,height*(i-index));
start=index;
}
stk.push({start,heights[i]});
}
while(!stk.empty()){
index=stk.top().first;
height=stk.top().second;
stk.pop();
maxArea=max(maxArea,height*(n-index));
}
return maxArea;
}
};
|
假设输入的矩阵的大小为m×n。该矩阵可以转换成m个直方图。如果采用单调栈法，那么求每个直方图的最大矩形面积需要O（n）的时间，因此这种解法的时间复杂度是O（mn）。
用单调栈法计算直方图中最大矩阵的面积需要O（n）的空间，同时还需要一个长度为n的数组heights，用于记录直方图中柱子的高度，因此这种解法的空间复杂度是O（n）。
单调栈 Monotonic Stack
496 下一个更大元素 I
暴力遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
//brute-force
int m=nums1.size(),n=nums2.size();
vector<int> res(m);
for(int i=0;i<m;i++){
int j=0;
while(j<n && nums1[i]!=nums2[j]){
j++;
}
while(j<n && nums1[i]>=nums2[j]){
j++;
}
res[i]=(j<n?nums2[j]:-1);
}
return res;
}
};
|
单调栈+哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> mp;
int n=nums2.size();
stack<int> monoStack;
for(int i=n-1;i>=0;i--){
while(!monoStack.empty() && nums2[i]>=monoStack.top()){
monoStack.pop();
}
mp[nums2[i]]=(monoStack.empty()?-1:monoStack.top());
monoStack.push(nums2[i]);
}
vector<int> res;
for(int i=0;i<nums1.size();i++){
res.push_back(mp[nums1[i]]);
}
return res;
}
};
|
看了单调栈方法后，自己独立写出来的☺️。
503 下一个更大元素 II
单调栈+循环数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n=nums.size();
vector<int> res(n);
stack<int> stk;
for(int i=n*2-1;i>=0;i--){
while(!stk.empty() && nums[i%n]>=stk.top()){
stk.pop();
}
res[i%n]=(stk.empty()?-1:stk.top());
stk.push(nums[i%n]);
}
return res;
}
};
|
没想到将循环数组拉直，不需要显性地将该循环数组「拉直」，只需要对下标%取模即可。下次注意！
907 Sum of Subarray Minimums
帮助理解的题解：
贡献法+单调栈+三种实现版本（Python/Java/C++/Go）
单调栈+贡献法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int n=arr.size();
vector<int> monoStack;
vector<int> left(n),right(n);
for(int i=0;i<n;i++){
//left: 第1个小于等于arr[i]的元素
while(!monoStack.empty() && arr[i]<=arr[monoStack.back()]){
monoStack.pop_back();
}
left[i]=i-(monoStack.empty()?-1:monoStack.back());
monoStack.push_back(i);
}
monoStack.clear();
for(int i=n-1;i>=0;i--){
//right: 第1个小于arr[i]的元素
while(!monoStack.empty() && arr[i]<arr[monoStack.back()]){
monoStack.pop_back();
}
right[i]=(monoStack.empty()?n:monoStack.back())-i;
monoStack.push_back(i);
}
long long MOD=1e9+7;
long long res=0;
for(int i=0;i<n;i++){
res=(res+(long long)arr[i]*right[i]*left[i])%MOD;
}
return res;
}
};
|
Author
Anjana
LastMod
2022-07-20
License
原创文章，如需转载请注明作者和出处。谢谢！