吴良超的学习笔记

Leetcode 解题报告(496, 975, 503)-next greater/smaller element

发表于 | ， ，

本文主要介绍在 LeetCode 题目 496. Next Greater Element I、975. Odd Even Jump、503. Next Greater Element II 中需要解决的共同问题：next greater element，就是对于一个数组中的每个 element，求出下标和值都比其大的一个 element，根据要求不同，这个问题又可分为 nearest of next greater elements 和 smallest of next greater elements，前者指的是 next greater elements 中离当前 element 最近的那个，后者指的是 next greater elements 中值最小的那个。两个问题都可通过 stack 解决，后者也可通过 treemap 解决。最后会将原来的问题进行的拓展，将原来的数据改成头尾相接的，其解决方法是将来的数组进行 duplicate, 然后把环解开，详细请看后文。

nearest of next greater elements

496. Next Greater Element I 要解决的就是 nearest of next greater element 的问题，如果直接进行暴力枚举，那时间复杂度是 $O(n^2)$, 而借助栈，能够让时间复杂度降为 $O(n)$, 其过程如下所示（栈用于存储元素的下标）

  1. 从后往前遍历数组
  2. 对于当前下标，假如其对应的值大于栈顶元素对应的值，则将栈顶元素出栈
  3. 重复步骤 2 直至栈顶元素对应的值大于等于当前下标对应的值或栈为空，如果是前者，则当前栈顶元素便是当前元素的 nearest of next greater elements, 如果是后者，这样的 element 不存在
  4. 将当前下标压栈，回到步骤 1

由于每个元素最多只会出栈一次和入栈一次，因此总体的时间复杂度是 $O(n)$, 这个方法减少了时间复杂度的关键点在于出栈，如对当前元素 e1，经过出栈后小于当前元素 e1 的元素都会出栈，假如下一个元素 e2 大于 e1，那么 e2 就不需要再跟那些已经出栈的元素进行比较了，因为那些元素小于 e1，也必定小于 e2。这样就减少了比较次数，将时间复杂度从原来的 $O(n^2)$ 降低到了 $O(n)$。

这里以题目 496. Next Greater Element I 为例，AC 的 pyhton 代码如下所示，

1
2
3
4
5
6
7
8
9
10
11
12
13
# traverse from right to left
class Solution(object):
    def nextGreaterElement(self, nums1, nums2):
        record, stack =  {}, []
        for i in xrange(len(nums2) - 1, -1, -1):
            while stack and stack[-1] < nums2[i]:
                stack.pop()
            if stack:
                record[nums2[i]] = stack[-1]
            else:
                record[nums2[i]] = -1
            stack.append(nums2[i])
        return [record[num] for num in nums1]

除了从后往前遍历，利用栈从前往后遍历也能解决这个问题，原理类似，AC 的 python 代码

1
2
3
4
5
6
7
8
9
10
11
# traverse from left to right
class Solution(object):
    def nextGreaterElement(self, nums1, nums2):
        stack, record = [], {}
        for num in nums2:
            while stack and stack[-1] < num:
                record[stack.pop()] = num
            stack.append(num)
        for num in stack:
            record[num] = -1
        return [record[num] for num in nums1]

smallest of next greater element

975. Odd Even Jump 要解决的是 smallest of next greater element 这一类问题，题目不是直接求解这个问题，而是结合了动态规划和这个问题。

动态规划比较容易想到，因为一般这类型是否能到达终点的题目都可以通过动态规划求解，如

回到题目 975. Odd Even Jump 由于在每个点有两种选择，即 odd jump 或者 even jump，则可以建立两个 dp 数组，odd_dp 和 even_dp, odd_dp[i] 表示从 i 以 odd jump 开始能够跳到终点，even_dp[i] 表示从 i 以 even jump 开始能够跳到终点。则 dp 递推式就很简单了

1
2
odd_dp[i] = even_dp[smallest of next greater elements of i]
even_dp[i] = odd_dp[greatest of next smaller elements of i]

最终统计 odd_dp 中为 true 的元素数量即可， 则问题就变成了 smallest of next greater elements 和 greatest of next smaller elements；解决的方法有两种，stack 和 treemap，两者的时间复杂度均为 $O(nlgn)$

stack

利用 stack 求解时, 不再像前面的问题一样可以直接在原来的数组上进行遍历，而是将每个元素的值带上其下标组成一个新的 tuple，然后根据 tuple 中的元素的值进行从小到大的排序，则此时便将问题转化为了 nearest of next greater elements，即只需要在当前元素后面那些元素中找到第一个下标比当前元素下标大的元素即可。排序的时间复杂素是 $O(nlgn)$, 遍历进行动态规划的时间复杂度是 $O(n)$, 因此总体的时间复杂度是 $O(nlgn)$, 求解题目的 python 代码如下所示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from collections import deque

class Solution(object):
    def oddEvenJumps(self, A):
        n = len(A)
        sorted_A = sorted([(v, i) for i, v in enumerate(A)])
        next_greater, greater_stack = [-1] * n, []
        idx = n - 1
        while idx >= 0:
            while greater_stack and greater_stack[-1] < sorted_A[idx][10]:
                greater_stack.pop()
            if greater_stack:
                next_greater[sorted_A[idx][11]] = greater_stack[-1]
            greater_stack.append(sorted_A[idx][12])
            idx -= 1
        
        sorted_A = sorted([(v, -i) for i, v in enumerate(A)]) # -i if for repeated elements
        next_smaller, smaller_stack = [-1] * n, []
        idx = 0
        while idx < n:
            while smaller_stack and smaller_stack[-1] < -1*sorted_A[idx][13]:
                smaller_stack.pop()
            if smaller_stack:
                next_smaller[-1*sorted_A[idx][14]] = smaller_stack[-1]
            smaller_stack.append(-1*sorted_A[idx][15])
            idx += 1
        odd_dp, even_dp = [False] * n, [False] * n
        odd_dp[-1], even_dp[-1] = True, True
        result = 1
        for i in xrange(n - 2, -1, -1):
            if next_greater[i] >= 0 and even_dp[next_greater[i]]:
                odd_dp[i] = True
                result += 1
            if next_smaller[i] >= 0 and odd_dp[next_smaller[i]]:
                even_dp[i] = True
        return result

treemap

另一种就是利用 treemap，treemap 是通过红黑树实现的一种数据结构, 红黑树是一棵二叉搜索树，因此能够在 $O(lgn)$ 时间复杂度内找到 next greater element。c++ 中内置的 map 的数据结构便是 treemap，python中没有 treemap 这种内置的数据结构。因此，对应求解题目的 c++ 代码如下，需要注意的是 map 的两个方法 lower_bound 和 upper_bound 含义如下

  • lower_bound 返回第一个大于等于当前值的 iterator
  • upper_bound 返回第一个大于当前值的 iterator

因此，下面的 --smaller 表示将返回的 iterator 往后移动，找到一个小于等于当前值的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <vector>
#include <map>

class Solution {
 public:
  int oddEvenJumps(std::vector<int>& A) {
    int n = A.size();
    std::vector<bool> odd_dp(n, false), even_dp(n, false);
    std::map<int, int> m;
    odd_dp[n-1] = true;
    even_dp[n-1] = true;
    int result = 1;
    for (int i = n - 1; i >= 0; i--) {
      auto greater = m.lower_bound(A[i]);
      if (greater != m.end() && even_dp[greater->second]) {
        result++;
        odd_dp[i] = true;
      }
      auto smaller = m.upper_bound(A[i]);
      if (smaller != m.begin() && odd_dp[(--smaller)->second]) even_dp[i] = true;
      m[A[i]] = i;
    }
    return result;
  }
};

array to circle

最后是 503. Next Greater Element II， 这个题目在第一题基础上将原来的数组首尾相连，并求每个元素的 next element，解决方法还是利用栈。

这种形成 circle 的问题一般都会想办法把 circle 去掉，如 213. House Robber II 就是通过列举可能的两种情况来把环去掉。而这道题目是通过首先在栈按原来数组顺序存储整个数组，栈顶元素为原来数组下标为 0 的元素，然后按照上面的方法从后往前遍历，这样做有效的原因是每个元素最多只能比较一圈回到自己本身，

对应的 python 代码如下所示

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def nextGreaterElements(self, nums):
        n = len(nums)
        result = [-1] * n
        stack = [nums[i] for i in xrange(n - 1, -1, -1)]
        for i in xrange(n - 1, -1, -1):
            while stack and stack[-1] <= nums[i]:
                stack.pop()
            if stack:
                result[i] = stack[-1]
            stack.append(nums[i])
        return result

summary

综上，本文主要介绍了 next greater element 问题及其衍生问题的求解方法，最原始的 nearest of next greater elements 通过 stack 能够在 $O(n)$ 的时间复杂度内求解；对于 smallest of next greater elements 问题，可通过 sort+stack 或 treemap 在 $O(nlgn)$ 的时间复杂度内解决；而如果将原来的 array 首尾相连，则只需要先在 stack 内存入整个 array 的元素（从后往前压入栈），因为每个元素最多只能比较一圈后回到自身。上面针对的是 next greater element 问题，但是 next smaller element 求解的原理和方法也是类似的，这里不再赘述。