leetcode-单调栈题型

单调栈分为单调递增栈和单调递减栈

  1. 单调递增栈即栈内元素保持单调递增的栈
  2. 同理单调递减栈即栈内元素保持单调递减的栈
    操作规则(下面都以单调递增栈为例)
  3. 如果新的元素比栈顶元素大,就入栈
  4. 如果新的元素较小,那就一直把栈内元素弹出来,直到栈顶比新元素小

    柱状图中最大的矩形

    给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
    求在该柱状图中,能够勾勒出来的矩形的最大面积。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    stack<int> st;
    for(int i = 0; i < nums.size(); i++)
    {
    while(!st.empty() && st.top() > nums[i])
    {
    st.pop();
    }
    st.push(nums[i]);
    }

对于一个高度,如果能得到向左和向右的边界
那么就能对每个高度求一次面积
遍历所有高度,即可得出最大面积
使用单调栈,在出栈操作时得到前后边界并计算面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int largestRectangleArea(vector<int>& heights)
{
int ans = 0;
vector<int> st;
heights.insert(heights.begin(), 0);
heights.push_back(0);
for (int i = 0; i < heights.size(); i++)
{
while (!st.empty() && heights[st.back()] > heights[i]) // 大的都弹出去
{
int cur = st.back();
st.pop_back();
int left = st.back() + 1;
int right = i - 1;
ans = max(ans, (right - left + 1) * heights[cur]);
}
st.push_back(i);
}
return ans;
}

滑动窗口最大值

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

1
2
3
4
5
6
7
8
9
10
11
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

遍历数组,将 数 存放在双向队列中,并用 L,R 来标记窗口的左边界和右边界。队列中保存的并不是真的 数,而是该数值对应的数组下标位置,并且数组中的数要从大到小排序。如果当前遍历的数比队尾的值大,则需要弹出队尾值,直到队列重新满足从大到小的要求。刚开始遍历时,L 和 R 都为 0,有一个形成窗口的过程,此过程没有最大值,L 不动,R 向右移。当窗口大小形成时,L 和 R 一起向右移,每次移动时,判断队首的值的数组下标是否在 [L,R] 中,如果不在则需要弹出队首的值,当前窗口的最大值即为队首的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
//使用双向队列。
vector<int> res;
deque<int> dq;
for (int i = 0; i < nums.size(); ++i) {
//如果窗口长度已经超过了k,则将最左边的元素移除
if (!dq.empty() && dq.front() == i - k) dq.pop_front();
//从后往前移除所有队列中小于当前元素的元素
while (!dq.empty() && nums[i] > nums[dq.back()]) dq.pop_back();
//在队列中添加当前元素
dq.push_back(i);
//如果窗口长度已经到达了k,则在结果中插入最大值(deque最前面的元素)
if (i >= k-1) res.push_back(nums[dq.front()]);
}
return res;
}

实现最大(小)栈

实现一个最大(小)栈,即可随时拿出当前栈中最大(小)的元素

比较简单的办法就是使用两个栈来实现这个特殊的栈
其中一个栈stack正常进出元素
另外一个栈stackMax(stackMin)在进元素的时候,与栈顶的元素做一个比较
如果大于(小于)栈顶元素,则正常入栈
如果小于(大于)栈顶元素,则将当前栈顶的元素再次入栈

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 MaxHeap {
stack<int> stack;
stack<int> stackMax;

int peekMax() {
return stackMax.top();
}

int push(int item) {
if (stack.empty()) {
stackMax.push(item);
} else {
if (item > stackMax.top()) {
stackMax.push(item);
} else {
stackMax.push(stackMax.top());
}
}
stack.push(item);
return item;
}

int peek() {
return stack.top();
}

int pop() {
stackMax.pop();
return stack.pop();
}
}
nephen wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
坚持原创技术分享,您的支持将鼓励我继续创作!