Fl0w3r

carpe diem

Stack

Posted on In
2.1k 4 mins.

引言

堆栈是一种常用的数据结构，以下我们会介绍 Stack 数据结构特点以及对于题目的原则，可以用于解决一系列常见的题目。

Stack 栈

  • 特性：LIFO（Last In First Out）
  • 适用于需要记录之前的状态，必要的时候可以回到之前的状态，或者利用之前的值
  • 不像 array，不能用 index 访问，只能每次拿栈顶元素

题外话：动态规划 Dynamic Programming

  • DP：记录之前所有状态，随时可能访问任何一个子问题，所以通常用 Array 或者 Hash Table，而且不会回到之前的状态，只会利用之前的值
  • Stack：每次只需要栈顶元素，并且每个状态只会被用 $O(1)$ 次

Stack Principle

定义好 Stack 的含义

  • 在 arr[i] 左侧所有比 arr[i] 大的数
  • 递归之前的函数状态（Call Stack）

实践应用

例题 739. Daily Temperatures

  • Find the distance to next greater element for each arr[i]
  • Stack Definition: All the elements (index) to the right of arr[i] that are greater than arr[i] (monotone increasing stack)
  • Top of Stack: Next greater element to the right of arr[i]

High Level Idea:

  1. Initialize stack

  2. For each element arr[i] backwards

    ​ Pop until stack is empty or top of stack > arr[i]

  3. Calculate distance from arr[i] to top of stack

  4. Repeat

  • 如果当前元素比栈顶大，则让小项逐个出栈，直到当前元素比栈顶小，停止出栈
  • 此时的栈顶元素就是当前项右边的第一个比自己大的元素索引，计算距离
  • 当前项入栈
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        stack<int> s;
        vector<int> res(n);
        for(int i = n - 1; i >= 0; i--) {
            while(!s.empty() && temperatures[i] >= temperatures[s.top()])
                s.pop();
            if(s.empty())
                res[i] = 0;
            else
                res[i] = s.top() - i;     
            
            s.push(i);   
        }
        return res;
    }
};

例题 735. Asteroid Collision

  • Stack Definition: All asteriods left so far
  • Top of Stack: Closest survived asteroid to the left of arr[i]

High Level Idea:

  1. Initialize Stack

  2. For each arr[i]

    if arr[i] > 0, push to stack

    else keep popping “smaller” until stack is empty or top element < 0

    special dealing with “equal”

    push arr[i] to stack if survived

  3. Repeat

可以类比成左右括号匹配：

  • 向右移动的小行星（左括号）：不会引发碰撞，直接入栈
  • 向左移动的小行星（右括号）：可能会和之前向右移动的小行星发生碰撞，特殊处理

因为答案需要碰撞后剩下的所有小行星，相当于栈里最后剩下的元素，所以可以直接用数组表示栈。

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        vector<int> res;

        for (auto a: asteroids) {
            if (a > 0)
                res.push_back(a);
            else {
                while (!res.empty() && res.back() > 0 && res.back() < -a)
                    res.pop_back();
                
                if (!res.empty() && res.back() == -a)
                    res.pop_back();
                else if (res.empty() || res.back() < -a)
                    res.push_back(a);    
            }
        }

        return res;
    }
};

总结

大家可以通过更多类似题目进行练习：

  1. Valid Parentheses (20)
  2. Next Greater Element I (496)
  3. Next Greater Element II (503)
  4. Decode String (394)
  5. Exclusive Time if Functions (636)
  6. Largest Rectangle in Histogram (84)
Related Posts