定义栈的单调性：从栈底到栈顶，如果元素单调递增（可以相等），记为单增栈，反之记为单减栈，下面的题解都采用这个说法
739. 每日温度
暴力
两层for循环，把至少需要等待的天数就搜出来了。时间复杂度是O(n^2)
class Solution {public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> res(n, 0);for (int i = 0; i < n; i++) {int j = i + 1;for (; j < n; j++) {res[i]++;if (temperatures[j] > temperatures[i])break;}if (j == n) res[i] = 0;}return res;}};
结果不出意外，超时了
单调栈
通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。
本题要寻找几天后才会有更高的温度，也就是求元素右边第一个比它大的元素与它的距离
维护一个单减栈
当栈为空或者栈顶元素不小于当前元素时，将元素压入栈中，否则，找到第一个比栈顶元素大的元素位置，不断计算栈顶元素与当前元素的距离，直到栈顶元素不小于当前元素为止。
因为要计算距离，直接在栈中存储元素下标即可。
class Solution {public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n = temperatures.size();vector<int> res(n, 0);stack<int> st;for (int i = 0; i < n; i++) {while (!st.empty() && temperatures[st.top()] < temperatures[i]) {res[st.top()] = i - st.top();st.pop();}st.push(i);}return res;}};
496. 下一个更大元素 I
暴力
先在nums2中找到对应元素，然后再看右边有没有比他大的
class Solution {public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();vector<int> res(n);for (int i = 0; i < n; i++) {int idx = 0, len = nums2.size();while (idx < len && nums1[i] != nums2[idx]) idx++; // 找nums1[i]while (idx < len && nums2[idx] <= nums1[i]) idx++; // 找第一个比nums1[i]大的res[i] = idx == len ? -1 : nums2[idx];}return res;}};
没有超时，是因为这是简单题吗？
单调栈
这道题与每日温度类似，定义一个单增栈，来记录nums2中每个元素右边第一个比它大的，
先用哈希表记录nums1数组元素的下标，正向遍历nums2：
- 栈为空或者栈顶元素大于等于当前访问的元素，那么入栈
- 栈不为空并且栈顶元素比当前元素小：
- 如果栈顶元素在nums1中出现过，则找到了这个元素在nums2中第一个比它大的，那么记录。anyway，为了维护栈的单调性，必须将较小元素弹出，压入当前元素
res初始化为-1，如果没有在右边找到比该元素大的，那么它就是-1不会被更新
class Solution {public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> res(nums1.size(), -1);unordered_map<int, int> um;stack<int> st;for (int i = 0; i < nums1.size(); i++) um[nums1[i]] = i;for (auto& num : nums2) {while (!st.empty() && st.top() < num) {if (um.count(st.top())) res[um[st.top()]] = num; // 如果栈顶元素在nums1中出现过，那么更新resst.pop();}st.push(num);}return res;}};
503. 下一个更大元素 II
单调栈
循环访问两遍数组即可，与496下一个最大元素I是类似的做法
在第一遍访问nums时，如果右边有比它大的元素，会把这个元素下标弹出去，也就是说，在第二圈不会将第一个比它大的元素更新成它左边的元素
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, -1);
stack<int> st; // 这个st来存储数组下标
for (int i = 0; i < 2 * n; i++) { // 遍历两遍数组
while (!st.empty() && nums[i % n] > nums[st.top()]) {
res[st.top()] = nums[i % n];
st.pop();
}
st.push(i % n);
}
return res;
}
};
42. 接雨水🍎
暴力（超时）
这道题需要先明确按行（水平）还是按列（竖直）来处理，按列处理比较容易理解
按列处理
这里用双指针来查找当前位置两侧最高的柱子，从而得到当前列能够存的雨水
由木桶原理我们知道，能够存多少水，取决于两侧最高的柱子中矮的那一个
比如求列4存的雨水，向两侧寻找，最高的列为3和7，高度分别为2,3。列4的高度为1那么，列4存储的雨水量为min(2, 3) - 1 = 1
这样计算每个列存储的雨水的量，然后累加，就是最后的结果
需要明确的一点是第一列和最后一列不存雨水
public:
int trap(vector<int>& height) {
int res = 0;
for (int i = 0; i < height.size(); i++) {
if (i == 0 || i == height.size() - 1) continue; // 第一列最后一列跳过
int leftHight = height[i], rightHight = height[i]; // 分别用来查找左右最大柱子高度
for (int left = i - 1; left >= 0; left--) // 寻找左边最大高度
if (height[left] > leftHight)
leftHight = height[left];
for (int right = i + 1; right < height.size(); right++) // 寻找右边最大高度
if (height[right] > rightHight)
rightHight = height[right];
res += min(leftHight, rightHight) - height[i];
}
return res;
}
};
时间复杂度O(n^2)，超时了
动态规划
双指针法会超时，是因为每次访问一个height[i]都要向两边遍历一次，而且不能“剪枝”，如果用两个数组来分别记录i左边和右边最大的柱子高度，最后再计算存水量，只需要循环三趟即可解决问题，时间复杂度降为O(N)，空间复杂度为O(N)
记left[i]表示i左边最高的柱子高度，那么left[i]可以由height[i - 1]和left[i - 1]得出：
- 如果height[i - 1] > left[i-1]的话，left[i] = heght[i -1]
- 如果height[i - 1] <= left[i-1]小的话，柱子i左边最高的柱子就是i-1左边最高的柱子，即 left[i] = left[i - 1]
可以得到状态转移方程为 left[i] = max(left[i-1], height[i-1])
当前状态由前一个状态得出，因此正向遍历
同理，记right[i]表示i右边最高的柱子高度，可以得到状态转移方程 right[i] = max(right[i + 1], height[i + 1])，反向遍历
最后计算每一列的存水量就ok了
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size(), res = 0;
vector<int> left(n, 0), right(n, 0);
for (int i = 1; i < n; i++) left[i] = max(height[i - 1], left[i - 1]);
for (int i = n - 2; i >= 0; i--) right[i] = max(height[i + 1], right[i + 1]);
for (int i = 1; i < n - 1; i++) {
int x = min(left[i], right[i]) - height[i];
res += max(x, 0); // 有可能不存水,这根柱子比两边的高
}
return res;
}
};
双指针
动态规划中需要维护两个数组来记录左边和右边最高的柱子，维护两只指针left、right和两个变量leftMax、rightMax也可以实现
左指针left向右移动，右指针right向左移动，每次移动后，都更新leftMax、rightMax
循环条件 left < right 两指针没有相遇时：
- 如果leftMax < rightMax：说明left左边的最高柱子比右边的矮，右边的还在更新中，right往左移动的时候，更新的rightMax只可能比leftMax更大，因此，这时候就可以计算left列的水量了，为leftMax - height[left]，这时要继续移动left
- 反之，和上一条同样的道理，这时候可以计算right处的水量，并将right左移
leftt和right相遇一定是在最高的柱子处，没有雨水
class Solution{
public:
int trap(vector<int>& height) {
int res = 0;
int n = height.size();
int left = 0, right = n - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = max(leftMax, height[left]); // 不断更新左边的最高柱子
rightMax = max(rightMax, height[right]); // 不断更新右边的最高柱子
if (leftMax < rightMax) {
res += leftMax - height[left++];
} else {
res += rightMax - height[right--];
}
}
return res;
}
};
单调栈
可以维护一个单减栈，栈中存储下标
当访问height[i]时，如果它比栈顶元素大，那么在栈顶的下一个元素，栈顶，height[i]之间会形成一个凹槽，用来存水，计算存水区域的面积（按行计算），假设取出栈顶元素，记为cur，高为min(height[i], height[st.top()]) - height[cur]，宽为 i - st.top - 1，蓄水面积是长乘宽
注：为什么用长乘宽呢，因为栈顶的几个元素可能高度相同，不能形成凹槽，这时候算出来的高度是0，也就是面积为0，只有当真正形成凹槽了，res才会真正的更新
class Solution{
public:
int trap(vector<int>& height) {
int res = 0;
int n = height.size();
stack<int> st; // 单调栈，存储的是下标
for (int i = 0; i < n; i++) {
while (!st.empty() && height[i] > height[st.top()]) {
int cur = st.top(); st.pop(); // 取栈顶元素
if (st.empty()) break; // 栈里没有其他元素了，说明存不了水，另一头堵不上
// 栈里还有其他元素，计算存水区域的面积 长 X 宽
int h = min(height[i], height[st.top()]) - height[cur]; // 高
int w = i - st.top() - 1; // 宽
res += h * w;
}
st.push(i);
}
return res;
}
};
84. 柱状图中最大的矩形
动态规划
用两个数组分别记录i左边第一个比该柱子矮的下标和右边第一个比该柱子矮的下标，然后循环处理以每个heights[i]为高的矩形面积，然后记录最大值
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
vector<int> minLeftIndex(heights.size());
vector<int> minRightIndex(heights.size());
int size = heights.size();
// 记录每个柱子 左边第一个小于该柱子的下标
minLeftIndex[0] = -1; // 注意这里初始化，防止下面while死循环
for (int i = 1; i < size; i++) {
int t = i - 1;
// 这里不是用if，而是不断向左寻找的过程
while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];
minLeftIndex[i] = t;
}
// 记录每个柱子 右边第一个小于该柱子的下标
minRightIndex[size - 1] = size; // 注意这里初始化，防止下面while死循环
for (int i = size - 2; i >= 0; i--) {
int t = i + 1;
// 这里不是用if，而是不断向右寻找的过程
while (t < size && heights[t] >= heights[i]) t = minRightIndex[t];
minRightIndex[i] = t;
}
// 求和
int result = 0;
for (int i = 0; i < size; i++) {
int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
result = max(sum, result);
}
return result;
}
};
单调栈
接雨水的题，使用的是单减栈，因为要找的是某个元素右边第一个大于该元素的值，寻找凹槽
对于本题，如果要确定以height[i]为高度的矩形面积，需要找到它的左右两端高度比它小的位置，我们从左向右遍历，那么就问题就转化为寻找某个元素在数组中第一个小于它的元素。
上图中，第三个元素值为5，左边是1，右边6，右边第一个小于它的元素是2，当扫描到2时，便可以确定以5为高度的矩形面积为 2 5 = 10
维护一个单增栈，正向遍历，记当前栈顶指向柱子高度为h，当heights[i] < h时，找到了栈顶右侧第一个比它矮的柱子，将栈顶弹出，新的栈顶是刚才弹出的栈顶左边第一个比它矮的柱子，于是可以计算出以h为高的*最大矩形面积，高为h，宽为 i - st.top() - 1，每次计算完矩形面积后，更新res。
单调栈中存储柱子下标，可以方便计算矩形面积
为了计算以第一根柱子和最后一根柱子为高度的矩形面积，在数组头部和尾部插入0，表示第一根柱子左边有比它小的元素
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int res = 0;
heights.insert(heights.begin(), 0); // 头部插入0
heights.push_back(0); // 尾部插入0
stack<int> st;
for (int i = 0; i < heights.size(); i++) {
while (!st.empty() && heights[st.top()] > heights[i]) { // 找到了第一个小于栈顶的元素，那么可以计算以栈顶为高的矩形面积
int h = heights[st.top()];
st.pop();
res = max(res, (i - st.top() - 1) * h);
}
st.push(i);
}
return res;
}
};
若有收获，就点个赞吧
0 人点赞
