栈训练

栈 (opens new window)

1.有效的括号 (opens new window)

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    let map = {
      "}": "{",
      ")": "(",
      "]": "["
    }

    let stack = []

    for (let i = 0; i < s.length; i++) {
      let str = s[i]
      // 遇到右括号
      if (map[str]) {
        // 左括号出栈判断匹配
        if (map[str] !== stack.pop()) {
          return false
        }
      } else {
        // 左括号进栈
        stack.push(str)
      }
    }

    return stack.length === 0
  };

2.下一个更大的元素 (opens new window)

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。

给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

 

示例 1：

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

• 单调栈

var nextGreaterElement = function (nums1: number[], nums2: number[]): number[] {
  let map = new Map()
  let arr = []

  arr.push(nums2[0])
  // 从下一个开始
  for (let i = 1; i < nums2.length; i++) {
    let top = arr[arr.length - 1]
    // 下一个小了，没找到记录一下
    if (nums2[i] < top) {
      arr.push(nums2[i])
    }
    // 下一个相等，没找到记录一下
    if (nums2[i] === top) {
      arr.push(nums2[i])
    }
    // 下一个大了，找到了
    if (nums2[i] > top) {
      // 记录一下
      map.set(top, nums2[i])
      arr.pop()
      // 继续看arr中没找到的，有没有符合条件的
      while (arr.length > 0 && arr[arr.length - 1] < nums2[i]) {
        // 找到了，记录并且删除
        map.set(arr[arr.length - 1], nums2[i])
        arr.pop()
      }
    }
    arr.push(nums2[i])
  }

  let res = []
  // 从map中找到num1的每个元素对应的下一个更到的元素
  for (let i = 0; i < nums1.length; i++) {
    if (map.has(nums1[i])) {
      res[i] = map.get(nums1[i])
    } else {
      res[i] = -1
    }
  }

  return res
};

优化一下上述代码：

var nextGreaterElement = function(nums1: number[], nums2: number[]): number[] {
    let map = new Map()
    let arr =[]

    arr.push(nums2[0])
    // 从下一个开始
    for(let i=1; i<nums2.length; i++) {
        // let top = arr[arr.length - 1]
        // // 下一个小了，没找到记录一下
        // if(nums2[i] < top) {
        //     arr.push(nums2[i])
        // }
        // // 下一个相等，没找到记录一下
        // if(nums2[i] === top) {
        //     arr.push(nums2[i])
        // }
        // 下一个大了，找到了
        // if(nums2[i] > top) {
            // 记录一下
            // map.set(top, nums2[i])
            // arr.pop()
            // 继续看arr中没找到的，有没有符合条件的
            while(arr.length > 0 && arr[arr.length - 1] < nums2[i]) {
                // 找到了，记录并且删除
                map.set(arr[arr.length - 1], nums2[i])
                arr.pop()
            }
        // }
        arr.push(nums2[i])
    }

    let res = []
    // 从map中找到num1的每个元素对应的下一个更到的元素
    for(let i=0; i<nums1.length; i++) {
        if(map.has(nums1[i])) {
            res[i] = map.get(nums1[i])
        } else {
            res[i] = -1
        }
    }

    return res
};

即经典的单调栈代码模板：

var nextGreaterElement = function (nums1: number[], nums2: number[]): number[] {
  let map = new Map()
  let stack = []

  for (let i = 0; i < nums2.length; i++) {
    while (stack.length > 0 && stack[stack.length - 1] < nums2[i]) {
      // 找到了，记录并且删除
      map.set(stack[stack.length - 1], nums2[i])
      stack.pop()
    }
    stack.push(nums2[i])
  }

  let res = []
  // 从map中找到num1的每个元素对应的下一个更到的元素
  for (let i = 0; i < nums1.length; i++) {
    res[i] = map.has(nums1[i]) ? map.get(nums1[i]) : -1
  }

  return res
};

3.下一个更大元素 II (opens new window)

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

 

示例 1:

输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2

• 单调栈

function nextGreaterElements(nums: number[]): number[] {
    let stack = []
    let len = nums.length
    let res = new Array(len).fill(-1)

    // stack.push(nums[0])
    // for(let i=1; i<len * 2; i++) {
    for(let i=0; i<len * 2; i++) {
        let n = nums[i % len]
        while(stack.length > 0 && n > nums[stack[stack.length - 1]]) {
            res[stack[stack.length - 1]] = n
            stack.pop()
        }
        stack.push(i % len)
    }

    return res
};

4.下一个更大元素 III (opens new window)

给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

 

示例 1：

输入：n = 12
输出：21
示例 2：

输入：n = 21
输出：-1
 

提示：

1 <= n <= 231 - 1

function nextGreaterElement(n: number): number {
  // 32位正数
  if (n > 2 ** 31 - 1) return -1

  // 数字转为字符串复杂度：log10n
  let arr = n.toString().split('').map(Number)
  nextPermutation(arr)

  let res = +arr.join('')

  return res > MAX ? -1 : res > n ? res : -1
};


// 下一个排列: https://leetcode.cn/problems/next-permutation/description/
function nextPermutation(nums: number[]): void {
  let i = nums.length - 1
  let flag = false
  for (; i > 0; i--) {
    if (nums[i] > nums[i - 1]) {
      // 找到比前一个大的数了
      // i 之后的肯定都符合 nums[i] >= nums[i+1]
      // 逆序即可以达到升序排列
      reverse(nums, i, nums.length - 1)
      flag = true
      break
    }
  }

  if (flag) {
    for (let j = i; j < nums.length; j++) {
      if (nums[j] > nums[i - 1]) {
        [nums[j], nums[i - 1]] = [nums[i - 1], nums[j]]
        return
      }
    }
  }


  reverse(nums, 0, nums.length - 1)
  return
};

function reverse(nums: number[], s: number, e: number) {
  while (s < e) {
    [nums[s], nums[e]] = [nums[e], nums[s]]
    s++
    e--
  }
}

2.每日温度 (opens new window)

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

 

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]
 

提示：

1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

• 单调栈

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
     if(!temperatures || temperatures.length < 1) return []

    let len = temperatures.length
    let res = new Array(len).fill(0)
    // 单调栈
    let stack = []
    stack.push(0)
    
    for(let i=1; i<len; i++) {
        // 右边的小或等，直接入栈
        if(temperatures[i] <= temperatures[stack[stack.length - 1]]) {
          stack.push(i)
        } else {
          // 找到第一个更大的了,准备出栈
          while(stack.length > 0) {
            let top = stack[stack.length - 1]
            if(temperatures[i] > temperatures[top]) {
              res[top] = i - top
              stack.pop()
            } else {
              break
            }
          }
          stack.push(i)
        }
    }

    return res
};

优化一下：

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
     if(!temperatures || temperatures.length < 1) return []

    let len = temperatures.length
    let res = new Array(len).fill(0)
    // 单调栈
    let stack = []
    stack.push(0)
    for(let i=1; i<len; i++) {
        // 找到比栈顶元素更大的第一个元素，将栈顶元素出栈，以此类推直至栈里面没有更大的了
        while(stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const top = stack.pop()
            res[top] = i - top
        }
        stack.push(i)
    }

    return res
};

3.逆波兰表达式求值 (opens new window)

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。
 

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
 

提示：

1 <= tokens.length <= 104
tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数
 

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function (tokens) {
    // 栈；
    // 遇到数字则入栈；
    // 遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。

    let stack = [];
    let op = '+-*/';
    for (let str of tokens) {
      if (op.indexOf(str) > -1) {
        // 出栈
        let b = stack.pop();
        let a = stack.pop();

        // 入栈
        if (str === '+') {
          stack.push(a + b)
        } else if (str === '-') {
          stack.push(a - b)
        } else if (str === '*') {
          stack.push(a * b)
        } else {
          stack.push(~~(a / b))
        }
      } else {
        stack.push(+str);
      }
    }

    // 出栈
    return stack.pop();
  };

4.盛最多水的容器 (opens new window)

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

• 双指针

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let n = height.length

    let left = 0;
    let right = n - 1
    let res = 0

    while(left < right) {
        let cur = (right - left) * Math.min(height[left], height[right])
        res = res > cur ? res : cur

        if(height[left] < height[right]) left++
        else right--
    }

    return res
};

5.接雨水 (opens new window)

• 单调栈：

var trap = function (height) {
  const len = height.length;
  if (len <= 2) return 0;

  let res = 0;
  const stack = [];
  for (let i = 0; i < len; i++) {
    // 找到第一个大的元素
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      let top = stack.pop();
      if (stack.length > 0) {
        let h = Math.min(height[stack[stack.length - 1]], height[i]) - height[top];
        let w = i - stack[stack.length - 1] - 1; // 注意减一，只求中间宽度
        res += h * w;
      }
    }
    stack.push(i);
  }
  return res;
};

• 双指针：

当前列雨水面积 = min(当前列左边柱子的最高高度，当前列右边柱子的最高高度) - 当前柱子高度。

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    let ans = 0;
    let left = 0, right = height.length - 1;

    let leftMax = 0, rightMax = 0;

    while (left < right) {
      leftMax = Math.max(leftMax, height[left]);
      rightMax = Math.max(rightMax, height[right]);

      if (leftMax < rightMax) {
        ans += leftMax - height[left];
        left++;
      } else {
        ans += rightMax - height[right];
        right--;
      }
    }

    return ans;
  };

6.柱状图中最大的矩形 (opens new window)

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

• 暴力求解

function largestRectangleArea(heights: number[]): number {
  if (!heights || heights.length < 1) return 0

  let res = 0
  for (let i = 0; i < heights.length; i++) {
    // 以heights[i]作为高度，计算可以左右扩散的最大宽度
    let left = i;
    // 向左边扩散
    while (left > 0 && heights[left - 1] >= heights[i]) {
      left--
    }
    // 向右扩散
    let right = i
    while (right < heights.length - 1 && heights[right + 1] >= heights[i]) {
      right++
    }

    // 计算heights[i]左右扩散的宽度
    let width = right - left + 1
    res = Math.max(res, width * heights[i])
  }

  return res
};

• 单调栈

function largestRectangleArea(heights: number[]): number {
  if (!heights || heights.length < 1) return 0

  let res = 0

  // 单调递减栈： 找每个柱子左右两边第一个小于该柱子的柱子
  let stack = []
  let arr = [0, ...heights, 0]

  for (let i = 0; i < arr.length; i++) {
    // 找到第一个小的元素
    while (stack.length > 0 && arr[i] < arr[stack[stack.length - 1]]) {
      let top = stack.pop()
      if(stack.length > 0) {
        res = Math.max(res, heights[top] * (i - stack[stack.length - 1] - 1))
      }
    }
    stack.push(i)
  }

  return res
};

7.去除重复字母 (opens new window)

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的
字典序
最小（要求不能打乱其他字符的相对位置）。

 

示例 1：

输入：s = "bcabc"
输出："abc"
示例 2：

输入：s = "cbacdcbc"
输出："acdb"
 

提示：

1 <= s.length <= 104
s 由小写英文字母组成
 

注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同

function smallestSubsequence(s: string): string {
    let stack: string[] = []
    let cache = new Map<string, boolean>()

    let counter = new Map<string, number>()
    for(let i=0; i<s.length; i++) {
        counter.set(s[i], (counter.get(s[i]) || 0) + 1)
    }


    for(let i=0; i<s.length; i++) {
        counter.set(s[i], counter.get(s[i]) - 1)

        if(cache.get(s[i])) continue

        while(stack.length > 0 && s[i] < stack[stack.length - 1]) {
            let top = stack[stack.length - 1]
            if(counter.get(top) === 0) break

            stack.pop()
            cache.set(top, false)
        }

        stack.push(s[i])
        cache.set(s[i], true)
    }

    return stack.join('')
};

8.拼接最大数 (opens new window)

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 1:

输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:
[9, 8, 6, 5, 3]
示例 2:

输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:
[6, 7, 6, 0, 4]
示例 3:

输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:
[9, 8, 9]
提示：

m == nums1.length
n == nums2.length
1 <= m, n <= 500
0 <= nums1[i], nums2[i] <= 9
1 <= k <= m + n

function maxNumber(nums1: number[], nums2: number[], k: number): number[] {
    let res = new Array(k).fill(0)
    let len1 = nums1.length
    let len2 = nums2.length

    // 假设t表示从nums1取几个数，则t取值范围： 
    // max(0, k-nums2.length) <= t <= min(k, nums1.length)
    let start = Math.max(0, k - len2)
    let end = Math.min(k, len1)
    for (let i = start; i <= end; i++) {
        // if (i > len1 || k - i > len2) continue
        let sub1 = maxSubArray(nums1, i)
        let sub2 = maxSubArray(nums2, k - i)
        let cur = merge(sub1, sub2)
        res = max(res, cur)
    }
    return res
};

// 求序列表示数最大的k位子序列： 单调栈
function maxSubArray(nums: number[], k: number): number[] {
    // 需要删除rm个数
    let rm = nums.length - t
    let stack = []

    for (let i = 0; i < nums.length; i++) {
        while (rm > 0 && stack.length > 0 && nums[i] > stack[stack.length - 1]) {
            stack.pop()
            rm--
        }
        stack.push(nums[i])
    }
    while (rm > 0) {
        stack.pop()
        rm--
    }
    return stack
}

// 合并两个序列，保持元素在各个序列中的相对位置不变，返回最大的序列
function merge(nums1, nums2) {
    let res = [];
    let p1 = 0, p2 = 0;

    while (p1 < nums1.length && p2 < nums2.length) {
        if (compare(nums1, p1, nums2, p2) >= 0) {
            res.push(nums1[p1++]);
        } else {
            res.push(nums2[p2++]);
        }
    }

    while (p1 < nums1.length) {
        res.push(nums1[p1++]);
    }

    while (p2 < nums2.length) {
        res.push(nums2[p2++]);
    }

    return res;
}

function compare(nums1: number[], p1: number, nums2: number[], p2: number) {
    while (p1 < nums1.length && p2 < nums2.length && nums1[p1] === nums2[p2]) {
        p1++;
        p2++;
    }

    if (p1 === nums1.length) return -1;
    if (p2 === nums2.length) return 1;

    return nums1[p1] - nums2[p2];
}

// 2个序列长度相同，返回表示数更大的序列
function max(nums1: number[], nums2: number[]): number[] {
    let len1 = nums1.length
    let len2 = nums2.length

    if (len1 < len2) return nums2
    if (len1 > len2) return nums1

    for (let i = 0; i < len1; i++) {
        if (nums1[i] > nums2[i]) return nums1
        if (nums1[i] < nums2[i]) return nums2
    }

    return nums1
}

9.移掉 K 位数字 (opens new window)

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

 
示例 1 ：

输入：num = "1432219", k = 3
输出："1219"
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
示例 2 ：

输入：num = "10200", k = 1
输出："200"
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 ：

输入：num = "10", k = 2
输出："0"
解释：从原数字移除所有的数字，剩余为空就是 0 。
 

提示：

1 <= k <= num.length <= 105
num 仅由若干位数字（0 - 9）组成
除了 0 本身之外，num 不含任何前导零

function removeKdigits(num: string, k: number): string {
    let stack = []

    for(let i = 0; i < num.length; i++) {
        while(k > 0 && stack.length > 0 && stack[stack.length - 1] > num[i]) {
            stack.pop()
            k--
        }
        stack.push(num[i])
    }
    while(k > 0) {
        stack.pop()
        k--
    }
    while(stack[0] === '0') {
        stack.shift()
    }
    return stack.length === 0 ? '0' : stack.join('')
}