Stack

引言

堆栈是一种常用的数据结构,以下我们会介绍 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)