跳转至

数据结构——栈

Min Stack和Max Stack

这个在LeetCode 155 Min Stack：

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) -- 将元素 x 推入栈中。

pop() -- 删除栈顶的元素。

top() -- 获取栈顶元素。

getMin() -- 检索栈中的最小元素。

class MinStack {
    stack<int> s1, s2;
public:
    /** initialize your data structure here. */
    MinStack() {}

    void push(int x) {
        if (s2.empty() || x <= s2.top()) s2.push(x);
        s1.push(x);
    }

    void pop() {
        if (s1.empty()) return;
        int res = s1.top();
        s1.pop();

        if (s2.empty()) return;
        if (res == s2.top()) s2.pop();
    }

    int top() {
        if (s1.empty()) return -1;
        return s1.top();
    }

    int getMin() {
        if (s2.empty()) return -1;
        return s2.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

虽然题目里并不要求考虑出错处理，比如栈是空的时候取最小值或栈顶值，但是还是需要去写出相应的处理代码。

LeetCode 716 Max Stack:

设计一个最大栈，支持 push、pop、top、peekMax 和 popMax 操作。

push(x) -- 将元素 x 压入栈中。

pop() -- 移除栈顶元素并返回这个值。

top() -- 返回栈顶元素。

peekMax() -- 返回栈中最大元素。

popMax() -- 返回栈中最大的元素，并将其删除。如果有多个最大元素，只要删除最靠近栈顶的那个。

相比于最小栈，多了一个删除最大元素的函数。

class MaxStack {
    stack<int> s1, s2;
public:
    /** initialize your data structure here. */
    MaxStack() {}

    void push(int x) {
        if (s2.empty() || x >= s2.top()) s2.push(x);
        s1.push(x);
    }

    int pop() {
        if (s1.empty()) return -1;

        int res = s1.top();
        s1.pop();
        if (res == s2.top()) s2.pop();
        return res;
    }

    int top() {
        if (s1.empty()) return -1;
        return s1.top();
    }

    int peekMax() {
        if (s2.empty()) return -1;
        return s2.top();
    }

    int popMax() {
        if (s2.empty()) return -1;

        int res = s2.top();
        s2.pop();
        stack<int> tmp;
        while (s1.top() != res) {
            tmp.push(s1.top());
            s1.pop();
        }
        s1.pop();
        while (!tmp.empty()) {
            push(tmp.top());
            tmp.pop();
        }
        return res;
    }
};

/**
 * Your MaxStack object will be instantiated and called as such:
 * MaxStack* obj = new MaxStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->peekMax();
 * int param_5 = obj->popMax();
 */

多了一个popMax的操作，需要一个临时栈存储s1的数据，删除最大值后，不是s1.push()，而是执行push。

用两个队列实现栈

LeetCode 225: 使用队列实现栈的下列操作：

  • push(x) -- 元素 x 入栈
  • pop() -- 移除栈顶元素
  • top() -- 获取栈顶元素
  • empty() -- 返回栈是否为空
class MyStack {
    queue<int> q1, q2;
public:
    /** Initialize your data structure here. */
    MyStack() {}

    /** Push element x onto stack. */
    void push(int x) {
        while (!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }
        q1.push(x);
        while (!q2.empty()) {
            q1.push(q2.front());
            q2.pop();
        }
    }

    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int res = q1.front();
        q1.pop();
        return res;
    }

    /** Get the top element. */
    int top() {
        return q1.front();
    }

    /** Returns whether the stack is empty. */
    bool empty() {
        return q1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

用两个栈实现队列

LeetCode 232: 使用栈实现队列的下列操作：

  • push(x) -- 将一个元素放入队列的尾部。
  • pop() -- 从队列首部移除元素。
  • peek() -- 返回队列首部的元素。
  • empty() -- 返回队列是否为空。
class MyQueue {
    stack<int> s1, s2;
public:
    /** Initialize your data structure here. */
    MyQueue() {}

    /** Push element x to the back of queue. */
    void push(int x) {
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
        s1.push(x);
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int res = s1.top();
        s1.pop();
        return res;
    }

    /** Get the front element. */
    int peek() {
        return s1.top();
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return s1.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

栈排序

餐盘栈

我们把无限数量 ∞ 的栈排成一行，按从左到右的次序从 0 开始编号。每个栈的的最大容量 capacity 都相同。

实现一个叫「餐盘」的类 DinnerPlates：

  • DinnerPlates(int capacity) - 给出栈的最大容量 capacity。
  • void push(int val) - 将给出的正整数 val 推入 从左往右第一个 没有满的栈。
  • int pop() - 返回 从右往左第一个 非空栈顶部的值，并将其从栈中删除；如果所有的栈都是空的，请返回 -1。
  • int popAtStack(int index) - 返回编号 index 的栈顶部的值，并将其从栈中删除；如果编号 index 的栈是空的，请返回 -1。
class DinnerPlates {
    vector<stack<int>> v;
    int pos; //存储最后一个存储数据的栈的下标
    int cap; //栈的容量
    int firstNotFull; //存储第一个没有满的栈的下标
public:
    DinnerPlates(int capacity) {
        cap = capacity;
        pos = 0;
        firstNotFull = 0;
        v.resize(100000);
    }

    void push(int val) {
        //如果第一个没有满的栈恰好是最后一个栈
        if (firstNotFull == pos) {
            v[pos].push(val);
            //加入元素后可能栈满，需要修改firstNotFull
            if (v[pos].size() == cap) ++firstNotFull;
        }
        //firstNotFull > pos只可能是pos的栈存满
        else if (firstNotFull > pos) {
            v[firstNotFull].push(val);
            ++pos;
            if (v[pos].size() == cap) ++firstNotFull;
        }
        //第一个非空的栈是最后一个非空栈前面的栈
        else {
            v[firstNotFull].push(val);
            //根据当前栈是否存满，来更新firstNotFull
            while (v[firstNotFull].size() == cap) ++firstNotFull;
        }
    }

    int pop() {
        //如果所有的栈都是空的
        if (v[pos].empty() && pos == 0) return -1;

        int res = v[pos].top();
        v[pos].pop();
        //更新pos，始终让pos指向最后一个非空的栈的下标
        while (v[pos].empty() && pos > 0) --pos;
        //更新firstNotFull
        if (firstNotFull - pos > 1) firstNotFull = pos + 1;

        return res;
    }

    int popAtStack(int index) {
        //访问的是空栈
        if (index > pos || v[index].empty()) return -1;

        int res = v[index].top();
        //index == pos等价于pop()
        if (index == pos) pop();
        else { //只能是index < pos的情况
            v[index].pop();
            //index <= firstNotFull需要更新
            if (index < firstNotFull) {
                firstNotFull = index;
            }
        }

        return res;
    }
};

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * DinnerPlates* obj = new DinnerPlates(capacity);
 * obj->push(val);
 * int param_2 = obj->pop();
 * int param_3 = obj->popAtStack(index);
 */

题目虽然是Hard，其实如果把变量的意义明确，分析清楚何时需要更新即可正确写出代码。

支持增量操作的栈

LeetCode 1381: Design a stack which supports the following operations.

Implement the CustomStack class:

  • CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
  • void push(int x) Adds x to the top of the stack if the stack hasn't reached the maxSize.
  • int pop() Pops and returns the top of stack or -1 if the stack is empty.
  • void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.
class CustomStack {
    stack<int> s;
    int capacity;
public:
    CustomStack(int maxSize) {
        capacity = maxSize;
    }

    void push(int x) {
        if (s.size() == capacity) return;
        s.push(x);
    }

    int pop() {
        if (s.empty()) return -1;
        int res = s.top();
        s.pop();
        return res;
    }

    void increment(int k, int val) {
        stack<int> tmp;
        if (s.size() <= k) {
            while (!s.empty()) {
                tmp.push(s.top() + val);
                s.pop();
            }
            while (!tmp.empty()) {
                s.push(tmp.top());
                tmp.pop();
            }
            return;
        }
        int cnt = 0;
        int n = s.size();
        while (cnt < n - k) {
            tmp.push(s.top());
            s.pop();
            ++cnt;
        }
        stack<int> store;
        while (!s.empty()) {
            store.push(s.top() + val);
            s.pop();
        }
        while(!store.empty()) {
            s.push(store.top());
            store.pop();
        }
        while (!tmp.empty()) {
            s.push(tmp.top());
            tmp.pop();
        }
    }
};

/**
 * Your CustomStack object will be instantiated and called as such:
 * CustomStack* obj = new CustomStack(maxSize);
 * obj->push(x);
 * int param_2 = obj->pop();
 * obj->increment(k,val);
 */

单调栈

单调栈的应用 https://www.cnblogs.com/wizarderror/category/1587954.html

《挑战程序设计竞赛》4.4.1里有单调栈。

单调栈常用的应用有：参考了https://blog.csdn.net/u011815404/category_8661014.html

  • 给定一组数，对于某个数，找到从左/右遍历第一个比它小/大的元素的位置
  • 给定一组数，针对每个数，寻找其与其左/右第一个比它小/大的数之间有多少个数
  • 给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列的长度最大
  • 给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列所有元素和最大

模板题目作为入门：（属于第一类）

  • 洛谷-P5788 [模板] 单调栈
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

int n = 3000005;
vector<int> f(n);
vector<int> sequence(n);

void monotonicStack()
{
    stack<int> s;
    for (int i = 1; i <= n; ++i) {
        if (s.empty()) 
            s.push(i);
        else {
            //注意栈里存放的是下标，所以比较的是sequence[s.top()]
            while (!s.empty() && sequence[i] > sequence[s.top()]) {
                f[s.top()] = i; s.pop(); 
            }
            s.push(i);
        }
    }
}

ostream & operator<<(ostream & os, const vector<int> & f)
{
    for (int i = 1; i <= n; ++i) os << f[i] << " ";
    os << endl;
    return os;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> sequence[i];
    monotonicStack();
    cout << f;

    return 0;
}

另外就是LeetCode里很经典的84.Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

img Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

img The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        heights.push_back(-1); //这样栈里面的所有元素都会弹出

        stack<int> s;
        int res = 0;
        int n = heights.size();
        for (int i = 0; i < n; ++i) {
            while (!s.empty() && heights[s.top()] > heights[i]) {
                int cur = s.top(); s.pop();
                res = max(res, heights[cur] * (s.empty() ? i : i - s.top() - 1));
            }
            s.push(i);
        }

        return res;
    }
};

解析：

单调栈的方法，考虑每个矩形，它可以往右延申的条件就是下一个临近的矩形的高度不小于它本身的高度，如果小于了，那么就需要去除矩形本身，始终维护一个高度递增的序列。

那么特殊情况，如果临近的两个矩形高度相等怎么办，比如2，4，4，3的情况，其实最右边的4往左延申等价于第一个4往右边延申，所以不会产生遗漏。

另外的技巧就是在序列末尾添加一个-1，保证最后所有的情况都会被检测到。

去检验算法的时候可以有几个很典型的测试用例：

1 2 3 4 5
3 0 3 2 5
2 1 2

典型题目：