03单调栈
# 03 单调栈
单调栈通过维持栈内值的单调递增(递减)性,在整体 O(n) 的时间内处理需要大小比较的问题。
# 739 每日温度 (opens new window)
给定每天的温度,求对于每一天需要等几天才可以等到更暖和的一天。如果该天之后不存在更暖和的天气,则记为 0。
输入是一个一维整数数组,输出是同样长度的整数数组,表示对于每天需要等待多少天。
输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]
解析:
本题可以通过维持一个单调递减的栈,表示每天的温度;而本题要求的是当前温度到更高温度的天数差,所以栈中的元素表示的是温度对应的日期,即温度在数组中的位置。单调递减的栈,所以栈顶表示的是栈内最低温度的日期。
从左向右遍历数组,对于日期 p ,如果 p 对应的温度高于栈顶的日期 q 对应的温度,则遇到了更暖和的一天,将 q 出栈并记录天数差为 p - q;如果 p 对应的温度低于栈顶的日期 q 对应的温度,或者栈为空,则将 p 压入栈中,然后继续考虑下一天的情况。
遍历完数组之后,栈内剩余的日期对应的温度都是递减的,说明他们之后不存在更暖和的天气。
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int> s;
int len = temperatures.size();
vector<int> ans(len);
for(int i=0;i<len;++i){
// 出栈栈内低于当前日期温度的日期,并计算天数差
while(!s.empty()){
int preTemp = temperatures[s.top()];
// 如果栈顶日期温度大于当前日期温度,停止出栈
if(preTemp >= temperatures[i]){
break;
}
ans[s.top()] = i - s.top();
s.pop();
}
s.push(i);
}
// 遍历完成之后,还未出栈的日期之后没有更高的温度
while(!s.empty()){
ans[s.top()] = 0;
s.pop();
}
return ans;
}
};
# 503 下一个更大元素 II (opens new window)
给定一个循环数组(最后一个元素的下一个元素是数组的第一个元素),输出每个元素的下一个更大元素。如果不存在,则输出 -1。
输入是一个一维整数数组,输出是同样长度的整数数组,表示对于原数组每位置的数下一个更大元素。
输入: [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2;数字 2 找不到下一个更大的数; 第二个 1 的下一个最大的数需要循环搜索,结果也是 2。
解析:
和每日温度相似,本题也可以通过维持一个单调递减的栈,表示原数组元素位置。
本题和739 每日温度 (opens new window)的区别在于本题待遍历的数组是一个循环数组,遍历循环数组的常用方式是将这个循环的圈拉直,即复制该序列的前 n-1 个元素拼接在原序列的后面。即用一个原数组的拷贝与其自身拼接成一个数组,例如将ABCDEF
循环数组拉直有ABCDEFABCDEF
,就有了A到A、B倒B……F到F的循环。
更简单可以避免增加空间开销,直接可以用模运算遍历数组,例如长度为 n 的循环数组元素表示为array[i%n]
按照上述循环数组遍历方法,从左向右遍历,对于当前位置 p,如果 p 对应的元素值大于单调栈栈顶 q 对应的元素值,则 q 遇到的更大值,在 q 位置保留 p 对应的值。如果栈为空,或者p 对应的元素值小于单调栈栈顶 q 对应的元素值,则将 p 压入栈,然后考虑下一个元素。
遍历完数组之后,栈内剩余的位置对应的元素值都是递减的,说明他们之后不存在更大的元素。
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
stack<int> s;
int len = nums.size();
// ans都初始化成 -1 就不用再去考虑没有出栈的元素了
vector<int> ans(len,-1);
for(int i=0;i<2*len-1;++i){
while(!s.empty()){
int preVal = nums[s.top()%len];
if(preVal >= nums[i%len]){
break;
}
ans[s.top()%len] = nums[i%len];
s.pop();
}
s.push(i);
}
return ans;
}
};
# 42 接雨水 (opens new window)
给定 n
个非负整数表示每个宽度为 1
的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
解析:
# 84 柱状图中最大的矩形 (opens new window)
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
输入:heights = [2,1,5,6,2,3] 输出:10 解释:最大的矩形为图中红色区域,面积为 10
解析:
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
stack<int> st;
int n = heights.size();
vector<int> left(n), right(n);
for(int i=0;i<n;++i){
while(!st.empty() && heights[st.top()] >= heights[i]){
st.pop();
}
left[i] = st.empty()?-1:st.top(); // -1 作为哨兵
st.push(i);
}
st = stack<int>();
for(int i=n-1;i>=0;--i){
while(!st.empty() && heights[st.top()] >= heights[i]){
st.pop();
}
right[i] = st.empty()?n:st.top(); // n 作为哨兵
st.push(i);
}
int ans = 0;
for(int i=0;i<n;++i){
ans = max(ans,(right[i]-left[i]-1)*heights[i]); // 面积=宽X高
}
return ans;
}
};
# 85 最大矩形 (opens new window)
给定一个仅包含 0
和 1
、大小为 rows x cols
的二维二进制矩阵,找出只包含 1
的最大矩形,并返回其面积。
输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出:6 解释:最大矩形如上图所示。
解析:
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
if(m==0 || n==0){
return 0;
}
vector<vector<int>> left(m,vector<int>(n,0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
left[i][j] = (j == 0 ? 0: left[i][j - 1]) + 1;
}
}
}
int ans = 0;
for(int j=0;j<n;++j){
stack<int> st;
vector<int> up(m), down(m);
for(int i=0;i<m;++i){
while(!st.empty() && left[st.top()][j] >= left[i][j]){
st.pop();
}
up[i] = st.empty()?-1:st.top();
st.push(i);
}
st = stack<int>();
for(int i=m-1;i>=0;--i){
while(!st.empty() && left[st.top()][j] >= left[i][j]){
st.pop();
}
down[i] = st.empty()?m:st.top();
st.push(i);
}
for(int i=0;i<m;++i){
int height = down[i] - up[i] - 1;
ans = max(ans,height*left[i][j]);
}
}
return ans;
}
};