堆栈

栈

基础

栈

先入后出；
线性数据结构；

栈顶和栈底

栈顶：栈的顶部；
栈底：栈的底部；

入栈和出栈

入栈：添加元素到栈顶；
出栈：删除栈顶元素；

栈的操作

方法	描述	时间复杂度
push()	元素入栈 (添加至栈顶)	$O(1)$
pop()	栈顶元素出栈	$O(1)$
peek()	访问栈顶元素	$O(1)$

链表实现和数组实现

数组实现

export class StackWithArray<T> {
  private _array: T[];
  private _index: number;
  private _size: number;
  constructor(size: number) {
    this._size = size;
    this._array = new Array(size);
    this._index = -1;
  }

  isEmpty() {
    return this._index === -1;
  }

  isFull() {
    return this._index === this._size - 1;
  }

  push(value: T) {
    if (this.isFull()) return false;
    this._index += 1;
    this._array[this._index] = value;
    return true;
  }

  pop() {
    if (this.isEmpty()) return null;
    const popValue = this._array[this._index];
    this._array[this._index] = undefined as T;
    this._index -= 1;
    return popValue;
  }

  peek() {
    if (this.isEmpty()) return null;
    return this._array[this._index];
  }
}

链表实现

import { DoublyLinkedList } from "../linked_list/doubly_linked_list";
import { DoublyLinkedListNode } from "../linked_list/doubly_linked_list_node";

export class StackWithLinkedList<T> {
  private list: DoublyLinkedList<T>;
  constructor() {
    this.list = new DoublyLinkedList<T>();
  }

  isEmpty() {
    return this.list.isEmpty();
  }

  push(value: DoublyLinkedListNode<T>) {
    const head = this.list.head;
    this.list.insert(value, head);
    return true;
  }

  pop() {
    if (this.isEmpty()) return null;
    const head = this.list.head;
    const deletedNode = head.next as DoublyLinkedListNode<T>;
    this.list.delete(deletedNode);
    return deletedNode;
  }

  peek() {
    if (this.isEmpty()) return null;
    return this.list.head.next as DoublyLinkedListNode<T>;
  }
}

两种实现对比

时间效率

数组实现扩容效率降低，但平均效率高；
链表实现效率相对较低但稳定；

空间效率

链表实现占用空间通常较大；

堆栈基本题目

有效的括号

题目

20；

思路

首先判断字符串长度是否为偶数，因为括号成对出现；
使用栈保存未匹配的左括号；
遍历到右括号时，判断当前字符是否与栈顶相同；
遍历完，判断栈是否为空；

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  if (s.length % 2 === 1) return false;
  let map = {
    "(": ")",
    "{": "}",
    "[": "]",
  };
  let stack = [];
  for (const char of s) {
    if (map[char] != null) {
      stack.push(map[char]);
    } else if (char !== stack.pop()) {
      return false;
    }
  }
  if (stack.length !== 0) return false;
  return true;
};

复杂度

时间：n；
空间：1；

基本计算器 1

题目

224；

思路

在基本计算器 2 的基础之上处理括号；
括号具有递归的性质，我们可以将括号看作另一个算式；
- 递归从 ( 开始，到 ) 结束；
- 使用 i 标记 ) 的位置；
- 使用 char === ")" 处理递归()时情况；
- 通过 i === str.length - 1 处理 ) 位于字符串最后的情况；

/**
 * @param {string} s
 * @return {number}
 */
var calculate = function (s) {
  const dfs = (str, i) => {
    let stack = [];
    let op = "+";
    let num = 0;
    for (; i < str.length; i++) {
      const char = str[i];
      if (char.match(/\d/)) {
        num = 10 * num + Number(char);
      }
      if (char.match(/[+\-*\/]/) || i === str.length - 1 || char === ")") {
        if (op === "+") {
          stack.push(num);
        } else if (op === "-") {
          stack.push(-num);
        } else if (op === "*") {
          stack.push(stack.pop() * num);
        } else if (op === "/") {
          const temp = stack.pop();
          const sign = Math.sign(temp);
          stack.push(Math.floor(Math.abs(temp) / num) * sign);
        }
        num = 0;
        op = char;
      }
      if (char === "(") {
        const res = dfs(str, i + 1);
        num = res[0];
        i = res[1];
        if (i === str.length - 1) i--;
      }
      if (char === ")") break;
    }
    return [stack.reduce((a, b) => a + b, 0), i];
  };

  return dfs(s, 0)[0];
};

复杂度

时间：n；
空间：n；

基本计算器 2

题目

227；

思路

计算表达式中，乘除优于加减；
使用栈保存表达式结果，加减压入栈，乘除取栈顶元素计算；
遍历字符串，使用 op 标记数字之前的运算符；
- +：num 压入栈；
- -：-num 压入栈；
- *：取出栈顶元素，计算 top _ num，将计算结果压入栈；
- /：取出栈顶元素，计算 top / num，将计算结果压入栈；
i === s.length - 1 进行最后一次相加；
最后将栈中整数累加；

/**
 * @param {sing} s
 * @return {number}
 */
var calculate = function (s) {
  let stack = [];
  let op = "+";
  let num = 0;
  let i = 0;
  for (; i < s.length; i++) {
    const char = s[i];
    if (char.match(/\d/)) {
      num = 10 * num + Number(char);
    }
    if (char.match(/[+\-*\/]/) || i === s.length - 1) {
      if (op === "+") {
        stack.push(num);
      } else if (op === "-") {
        stack.push(-num);
      } else if (op === "*") {
        stack.push(stack.pop() * num);
      } else if (op === "/") {
        const temp = stack.pop();
        const sign = Math.sign(temp);
        stack.push(Math.floor(Math.abs(temp) / num) * sign);
      }
      num = 0;
      op = char;
    }
  }

  return stack.reduce((a, b) => a + b, 0);
};

复杂度

时间：n；
空间：n；

最小栈

题目

155；

思路

使用一个辅助栈，存储栈各个状态的最小值；

var MinStack = function () {
  this.stack = [];
  this.min = [Infinity];
};

/**
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function (val) {
  this.stack.push(val);
  this.min.push(Math.min(this.min[this.min.length - 1], val));
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  this.stack.pop();
  this.min.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
  return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
  return this.min[this.min.length - 1];
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

复杂度

时间：n；
空间：n；

用栈实现队列

题目

232；

思路

使用两个栈 inStack，outStack；
inStack 用于输入，outStack 用于输出；
- 栈先入后出，inStack 压入 outStack；
- inStack 先入，在 outStack 变为后入的了；
- outStack 后入先出，从而实现整体上的先入先出；
进行 pop 和 peek 操作时，将 inStack 压入 outStack；

var MyQueue = function () {
  this.in = [];
  this.out = [];
};

/**
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
  this.in.push(x);
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function () {
  if (this.out.length === 0) {
    while (this.in.length > 0) {
      this.out.push(this.in.pop());
    }
  }
  return this.out.pop();
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function () {
  if (this.out.length === 0) {
    while (this.in.length > 0) {
      this.out.push(this.in.pop());
    }
  }
  return this.out[this.out.length - 1];
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
  return this.in.length === 0 && this.out.length === 0;
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

复杂度

时间：1；
空间：n；

字符串解码

题目

394；

思路

使用两个栈 resStack，numStack；
resStack 保存左括号已经解码的字符串，numStack 存储左括号前的数字；
定义 num 存储当前数字，res 存储当前编码字符串；
遍历 s；
- 遇到数字，累加到 num；
- 遇到左括号，res 压入 resStack，num 压入 numStack，res = ""，num = 0；
- 遇到字符，cur += cur；
- 遇到右括号，resStack 取出 curRes，numStack 取出 curNum，res = curRes + res *curNum；

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function (s) {
  let resStack = [];
  let numStack = [];
  let res = "";
  let num = 0;

  for (const c of s) {
    if (c.match(/\d/)) {
      num = num * 10 + Number(c);
    } else if (c === "[") {
      resStack.push(res);
      numStack.push(num);
      res = "";
      num = 0;
    } else if (c === "]") {
      const curRes = resStack.pop();
      const curNum = numStack.pop();
      let temp = "";
      for (let i = 0; i < curNum; i++) {
        temp += res;
      }
      res = curRes + temp;
    } else {
      res += c;
    }
  }
  return res;
};

复杂度

时间：n；
空间：n；

最长有效括号

题目

32；

思路

定义 res 维护最长有效括号的长度；
定义 stack 判断括号对是否匹配，栈底元素存储有效括号子串开始元素的前一个索引；
遍历字符串；
- 遇到左括号，压入索引；
- 遇到右括号，与栈顶元素匹配，弹出栈顶元素；
  - 如果弹出之后栈为空，说明无法完成匹配，使用右括号索引作为下一子串开始元素的前一个索引；
  - 反之完成匹配，当前长度为 cur-stack[-1]，res = max(res，cur-stack[-1])；

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  const stack = [-1];
  let res = 0;
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (c === "(") {
      stack.push(i);
    } else {
      stack.pop();
      if (stack.length === 0) {
        stack[0] = i;
      } else {
        const len = i - stack[stack.length - 1];
        res = Math.max(res, len);
      }
    }
  }

  return res;
};

复杂度

时间：n；
空间：n；

删除字符串中的所有相邻重复项

题目

1047；

思路

基于栈，如果当前字符和栈顶字符相同，删除栈顶，反之进栈；

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function (s) {
  const stack = [];
  for (const ch of s) {
    if (ch === stack.at(-1)) stack.pop();
    else stack.push(ch);
  }

  return stack.join("");
};

复杂度

时间：n；
空间：1；

简化路径

题目

71；

思路

根据 / 划分字符串，并移除空字符串；
遍历字符串数组，遇到。。移除栈顶元素，反之添加至栈顶；

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function (path) {
  path = path.split("/").filter((value) => value.length !== 0);
  const res = [];
  for (const sub of path) {
    if (sub === ".") continue;
    if (sub === "..") res.pop();
    else res.push(sub);
  }

  return "/" + res.join("/");
};

复杂度

时间：n；
空间：n；

单调栈

基础

单调递增栈

只有比栈顶元素小的元素才能直接进栈；
否则将栈中比当前元素小的元素出栈，再将当前元素进栈；

单调递减栈

只有比栈顶元素大的元素才能直接进栈；
否则将栈中比当前元素大的元素出栈，再将当前元素进栈；

使用场景

概述

寻找左(右)侧第一个比当前元素大(小)的元素；

寻找左侧第一个比当前元素大的元素

从左到右比遍历元素，构造单调递增栈；
目标元素即当插入当前元素时的栈顶元素；
若栈为空，则不存在对应元素；

寻找左侧第一个比当前元素小的元素

从左到右遍历元素，构造单调递减栈；
目标元素即当插入当前元素时的栈顶元素；
若栈为空，则不存在对应元素；

寻找右侧第一个比当前元素大的元素

从左到右比遍历元素，构造单调递增栈；
目标元素即当弹出当前元素时的插入元素；
若当前元素为被弹出，则不存在对应元素；

寻找右侧第一个比当前元素小的元素

从左到右遍历元素，构造单调递减栈；
目标元素即当弹出当前元素时的插入元素；
若当前元素未被弹出，则不存在对应元素；

口诀

从左到右遍历元素；
比当前元素大，用单调递增栈，反之单调递减栈；
左侧即插入栈时的栈顶元素，右侧则弹出栈时的插入元素；

单调栈模板

单调递增栈

def monotoneIncreasingStack(nums):
    stack = []
    for num in nums:
        while stack and num >= stack[-1]:
            stack.pop()
        stack.append(num)

单调递减栈

def monotoneDecreasingStack(nums):
    stack = []
    for num in nums:
        while stack and num <= stack[-1]:
            stack.pop()
        stack.append(num)

等于号的取舍

求左侧第一个大于或小于，使用等于号；
求右侧，不使用等于号；

单调栈题目

下一个更大元素 1

题目

496；

思路

使用单调递增栈；
因为 nums1 是 nums2 的子集；
遍历 nums2，构造单调递增栈，求出 nums2 每个元素右侧第一个更大元素，存储到哈希表中；

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function (nums1, nums2) {
  let map = {};
  let stack = [];
  let res = [];

  for (const num of nums2) {
    while (stack && num > stack[stack.length - 1]) {
      map[stack[stack.length - 1]] = num;
      stack.pop();
    }
    stack.push(num);
  }

  for (const num of nums1) {
    res.push(map[num] || -1);
  }
  return res;
};

复杂度

时间：n；
空间：n；

下一个更大元素 2

题目

503；

思路

因为是循环数组，可以直接复制一份数组添加至原始数组后面；
或者从 0 遍历至 2n-1，通过 i%size，映射至 [0，n)；

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var nextGreaterElements = function (nums) {
  const n = nums.length;
  const res = new Array(n).fill(-1);
  const maxStack = [];
  for (let i = 0; i < 2 * n; i++) {
    while (maxStack.length !== 0 && nums[i % n] > nums[maxStack.at(-1)]) {
      const index = maxStack.pop();
      res[index] = nums[i % n];
    }
    maxStack.push(i % n);
  }

  return res;
};

复杂度

时间：n；
空间：n；

每日温度

题目

739；

思路

使用单调递增栈；
查找右侧第一个比当前元素大的元素，记录其差值，不存在即 0；
stack 记录 temperature 的索引值；

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
  let res = new Array(temperatures.length).fill(0);
  let stack = [];
  for (let i = 0; i < temperatures.length; i++) {
    const tem = temperatures[i];
    while (stack && tem > temperatures[stack[stack.length - 1]]) {
      const index = stack.pop();
      res[index] = i - index;
    }
    stack.push(i);
  }
  return res;
};

复杂度

时间：n；
空间：n；

接雨水

题目

42；

思路

基于单调递增栈；
假设当前柱体为 C，出栈柱体为 B，出栈为新的栈顶柱体为 A；
- C 是 B 右侧第一个大于 B 的柱体；
- A 是 B 左侧第一个大于 B 的柱体；
B 出栈后，以 A 为左边界，C 为右边界；
左右边界与 B 的高度差为深度，计算并更新接水面积；

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let res = 0;
  const maxStack = [];
  for (let i = 0; i < height.length; i++) {
    while (
      maxStack.length > 0 &&
      height[i] > height[maxStack[maxStack.length - 1]]
    ) {
      const mid = maxStack.pop();
      if (maxStack.length === 0) break;
      const left = maxStack[maxStack.length - 1];
      const right = i;
      const sub = Math.min(height[left], height[right]) - height[mid];
      const volume = sub * (right - 1 - (left + 1) + 1);
      res += volume;
    }
    maxStack.push(i);
  }
  return res;
};

复杂度

时间：n；
空间：n；

滑动窗口最大值

题目

239；

思路

首先将前 k 个元素加入单调递增栈，保存数组值和索引构建的元组；
当栈顶顶索引不在滑动窗口范围，不断删除栈顶元素；
将最大值添加至答案数组；

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  const push = (stack, num, index) => {
    while (stack.length !== 0 && num >= maxStack[maxStack.length - 1][0]) {
      stack.pop();
    }
    stack.push([num, index]);
  };

  const maxStack = [];
  for (let i = 0; i < k; i++) {
    push(maxStack, nums[i], i);
  }
  const res = [maxStack[0][0]];
  for (let i = k; i < nums.length; i++) {
    push(maxStack, nums[i], i);
    while (maxStack[0][1] < i - k + 1) {
      maxStack.shift();
    }
    res.push(maxStack[0][0]);
  }

  return res;
};

复杂度

时间：nlogn；
空间：k；

柱状图中的最大矩形

题目

84；

思路

面积最大矩形的高度一定是 height[i]；
对于每个 i，寻找左侧第一个小于 i 的元素 left，右侧第一个小于 i 的元素 right
对与索引 i，其最大矩形为 height[i]*(right-left-1)；
height 首尾添加一个 0 处理边界情况；
遍历数组，维护最大矩形面积，思路类似于接雨水；

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function (heights) {
  heights.push(0);
  heights.unshift(0);

  let res = 0;
  let minStack = [];
  for (let i = 0; i < heights.length; i++) {
    while (minStack.length !== 0 && heights[i] < heights[minStack.at(-1)]) {
      const mid = minStack.pop();
      const right = i;
      const left = minStack.at(-1);
      res = Math.max(res, heights[mid] * (right - left - 1));
    }
    minStack.push(i);
  }

  return res;
};

复杂度

时间：n；
空间：n；

最大矩形

题目

85；

思路

以第 i 行为基准线，统计每列在基准线以上 1 的个数；
这样就转换为柱状图的最大矩形问题；

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function (matrix) {
  const largestRectangleArea = function (heights) {
    heights.push(0);
    heights.unshift(0);

    let res = 0;
    let minStack = [];
    for (let i = 0; i < heights.length; i++) {
      while (minStack.length !== 0 && heights[i] < heights[minStack.at(-1)]) {
        const mid = minStack.pop();
        const right = i;
        const left = minStack.at(-1);
        res = Math.max(res, heights[mid] * (right - left - 1));
      }
      minStack.push(i);
    }

    return res;
  };

  const m = matrix.length;
  const n = matrix[0].length;
  const heightList = Array.from({ length: m }, () => new Array(n).fill(0));
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0) heightList[i][j] = Number(matrix[i][j]);
      else if (matrix[i][j] === "1") {
        heightList[i][j] = heightList[i - 1][j] + 1;
      }
    }
  }

  let res = 0;
  for (let i = 0; i < m; i++) {
    const height = heightList[i];
    res = Math.max(res, largestRectangleArea(height));
  }

  return res;
};

复杂度

时间：mn；
空间：mn；

栈​

基础​

栈​

栈顶和栈底​

入栈和出栈​

栈的操作​

链表实现和数组实现​

数组实现​

链表实现​

两种实现对比​

时间效率​

空间效率​

堆栈基本题目​

有效的括号​

题目​

思路​

复杂度​

基本计算器 1​

题目​

思路​

复杂度​

基本计算器 2​

题目​

思路​

复杂度​

最小栈​

题目​

思路​

复杂度​

用栈实现队列​

题目​

思路​

复杂度​

字符串解码​

题目​

思路​

复杂度​

最长有效括号​

题目​

思路​

复杂度​

删除字符串中的所有相邻重复项​

题目​

思路​

复杂度​

简化路径​

题目​

思路​

复杂度​

单调栈​

基础​

单调递增栈​

单调递减栈​

使用场景​

概述​

寻找左侧第一个比当前元素大的元素​

寻找左侧第一个比当前元素小的元素​

寻找右侧第一个比当前元素大的元素​

寻找右侧第一个比当前元素小的元素​

口诀​

单调栈模板​

单调递增栈​

单调递减栈​

等于号的取舍​

单调栈题目​

下一个更大元素 1​

题目​

思路​

复杂度​

下一个更大元素 2​

题目​

思路​

复杂度​

每日温度​

题目​

思路​

复杂度​

接雨水​

题目​

思路​

栈

基础

栈

栈顶和栈底

入栈和出栈

栈的操作

链表实现和数组实现

数组实现

链表实现

两种实现对比

时间效率

空间效率

堆栈基本题目

有效的括号

题目

思路

复杂度

基本计算器 1

题目

思路

复杂度

基本计算器 2

题目

思路

复杂度

最小栈

题目

思路

复杂度

用栈实现队列

题目

思路

复杂度

字符串解码

题目

思路

复杂度

最长有效括号

题目

思路

复杂度

删除字符串中的所有相邻重复项

题目

思路

复杂度

简化路径

题目

思路

复杂度

单调栈

基础

单调递增栈

单调递减栈

使用场景

概述

寻找左侧第一个比当前元素大的元素

寻找左侧第一个比当前元素小的元素

寻找右侧第一个比当前元素大的元素

寻找右侧第一个比当前元素小的元素

口诀

单调栈模板

单调递增栈

单调递减栈

等于号的取舍

单调栈题目

下一个更大元素 1

题目

思路

复杂度

下一个更大元素 2

题目

思路

复杂度

每日温度

题目

思路

复杂度

接雨水

题目

思路