旺崽的博客

要么天赋异禀，要么天道酬勤

0%

发表于 分类于 Valine：

题目链接

给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定不同的子数组为好子数组。

（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3）

返回 A 中好子数组的数目。

示例 1：

1
2
3
输入：A = [1,2,1,2,3], K = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

示例 2：

1
2
3
输入：A = [1,2,1,3,4], K = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].

思维+双指针~
利用双指针，当我们固定左端点时，可以找到恰好存在 K 个不同整数的最大右边界 $R$，那么我们只需找到最小左边界 $L$，答案就是 $R-L+1$，那么这个最小左边界怎么找呢，我们可以再加一个指针，这个指针指向恰好存在 K-1 个不同整数的最大右边界 $R’$，答案就是 $R-R’$，AC代码如下：

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
class Solution {
public:
    int subarraysWithKDistinct(vector<int> &A, int K) {
        int n = A.size();
        vector<int> num1(n + 1), num2(n + 1);
        int sum1 = 0, sum2 = 0;
        int l1 = 0, l2 = 0, r = 0, ans = 0;
        while (r < n) {
            if (!num1[A[r]]) sum1++;
            num1[A[r]]++;
            if (!num2[A[r]]) sum2++;
            num2[A[r]]++;
            while (sum1 > K) {
                num1[A[l1]]--;
                if (!num1[A[l1]]) sum1--;
                l1++;
            }
            while (sum2 > K - 1) {
                num2[A[l2]]--;
                if (!num2[A[l2]]) sum2--;
                l2++;
            }
            ans += l2 - l1;
            r++;
        }
        return ans;
    }
};

发表于 分类于 Valine：

题目链接

给你一个二维整数数组 orders ，其中每个 orders[i] = [price_i, amount_i, orderType_i] 表示有 amount_i 笔类型为 orderType_i 、价格为 price_i 的订单。

订单类型 orderTypei 可以分为两种：

  • 0 表示这是一批采购订单 buy
  • 1 表示这是一批销售订单 sell
    注意，orders[i] 表示一批共计 amount_i 笔的独立订单，这些订单的价格和类型相同。对于所有有效的 i ，由 orders[i] 表示的所有订单提交时间均早于 orders[i+1] 表示的所有订单。

存在由未执行订单组成的 积压订单 。积压订单最初是空的。提交订单时，会发生以下情况：

如果该订单是一笔采购订单 buy ，则可以查看积压订单中价格 最低 的销售订单 sell 。如果该销售订单 sell 的价格 低于或等于 当前采购订单 buy 的价格，则匹配并执行这两笔订单，并将销售订单 sell 从积压订单中删除。否则，采购订单 buy 将会添加到积压订单中。
反之亦然，如果该订单是一笔销售订单 sell ，则可以查看积压订单中价格 最高 的采购订单 buy 。如果该采购订单 buy 的价格 高于或等于 当前销售订单 sell 的价格，则匹配并执行这两笔订单，并将采购订单 buy 从积压订单中删除。否则，销售订单 sell 将会添加到积压订单中。
输入所有订单后，返回积压订单中的 订单总数 。由于数字可能很大，所以需要返回对 $10^9 + 7$ 取余的结果。

示例 1：

在这里插入图片描述

1
2
3
4
5
6
7
8
输入：orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
输出：6
解释：输入订单后会发生下述情况：
- 提交 5 笔采购订单，价格为 10 。没有销售订单，所以这 5 笔订单添加到积压订单中。
- 提交 2 笔销售订单，价格为 15 。没有采购订单的价格大于或等于 15 ，所以这 2 笔订单添加到积压订单中。
- 提交 1 笔销售订单，价格为 25 。没有采购订单的价格大于或等于 25 ，所以这 1 笔订单添加到积压订单中。
- 提交 4 笔采购订单，价格为 30 。前 2 笔采购订单与价格最低（价格为 15）的 2 笔销售订单匹配，从积压订单中删除这 2 笔销售订单。第 3 笔采购订单与价格最低的 1 笔销售订单匹配，销售订单价格为 25 ，从积压订单中删除这 1 笔销售订单。积压订单中不存在更多销售订单，所以第 4 笔采购订单需要添加到积压订单中。
最终，积压订单中有 5 笔价格为 10 的采购订单，和 1 笔价格为 30 的采购订单。所以积压订单中的订单总数为 6 。

示例 2：

1
2
3
4
5
6
7
8
输入：orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]
输出：999999984
解释：输入订单后会发生下述情况：
- 提交 109 笔销售订单，价格为 7 。没有采购订单，所以这 109 笔订单添加到积压订单中。
- 提交 3 笔采购订单，价格为 15 。这些采购订单与价格最低（价格为 7 ）的 3 笔销售订单匹配，从积压订单中删除这 3 笔销售订单。
- 提交 999999995 笔采购订单，价格为 5 。销售订单的最低价为 7 ，所以这 999999995 笔订单添加到积压订单中。
- 提交 1 笔销售订单，价格为 5 。这笔销售订单与价格最高（价格为 5 ）的 1 笔采购订单匹配，从积压订单中删除这 1 笔采购订单。
最终，积压订单中有 (1000000000-3) 笔价格为 7 的销售订单，和 (999999995-1) 笔价格为 5 的采购订单。所以积压订单中的订单总数为 1999999991 ，等于 999999984 % (109 + 7) 。

水题，只要用两个优先队列分别维护 sell 订单和 buy 订单即可，AC 代码如下：

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
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int getNumberOfBacklogOrders(vector<vector<int>> &orders) {
        long long ans = 0, mod = 1e9 + 7;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> sell;
        priority_queue<pair<int, int>, vector<pair<int, int>>, less<>> buy;
        for (auto &i:orders) {
            if (i[2] == 0) {
                if (sell.empty()) buy.push({i[0], i[1]});
                else {
                    while (!sell.empty() && i[0] >= sell.top().first && i[1]) {
                        if (i[1] >= sell.top().second) {
                            i[1] -= sell.top().second;
                            sell.pop();
                        } else {
                            auto p = sell.top();
                            sell.pop();
                            sell.push({p.first, p.second - i[1]});
                            i[1] = 0;
                        }
                    }
                    if (i[1] > 0) buy.push({i[0], i[1]});
                }
            } else {
                if (buy.empty()) sell.push({i[0], i[1]});
                else {
                    while (!buy.empty() && i[0] <= buy.top().first && i[1]) {
                        if (i[1] >= buy.top().second) {
                            i[1] -= buy.top().second;
                            buy.pop();
                        } else {
                            auto p = buy.top();
                            buy.pop();
                            buy.push({p.first, p.second - i[1]});
                            i[1] = 0;
                        }
                    }
                    if (i[1] > 0) sell.push({i[0], i[1]});
                }
            }
        }
        while (!buy.empty()) ans = (ans + buy.top().second) % mod, buy.pop();
        while (!sell.empty()) ans = (ans + sell.top().second) % mod, sell.pop();
        return ans;
    }
};

发表于 分类于 Valine：

题目链接

根据逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

1
2
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

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

示例 2：

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

示例 3：

1
2
3
4
5
6
7
8
9
10
11
输入：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

简单栈操作，用一个数字栈存所有数字，每碰到一个运算符，就从栈中取两个数计算出一个结果再存到栈里，最后返回栈顶即可，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        num = []
        for i in tokens:
            if i != '+' and i != '-' and i != '*' and i != '/':
                num.append(int(i))
            else:
                a = num[-1]
                num.pop()
                b = num[-1]
                num.pop()
                if i == '+':
                    num.append(a + b)
                elif i == '-':
                    num.append(b - a)
                elif i == '/':
                    num.append(int(b / a))
                elif i == '*':
                    num.append(a * b)
        return num[-1]

发表于 分类于 Valine：

题目链接

给你一个正整数 $n$ ，生成一个包含 $1$ 到 $n^2$ 所有元素，且元素按顺时针顺序螺旋排列的 $n$ x $n$ 正方形矩阵 $matrix$ 。

示例 1：

1
2
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

1
2
输入：n = 1
输出：[[1]]

螺旋填数有一些性质我们必须要知道：

  • 在填数的过程中有上，下，左，右四个边界，且这四个边界会逐渐缩至一个点
  • 填数始终遵循以下顺序(顺时针)：
    a.从左到右
    b.从上到下
    c.从右到左
    d.从下到上

了解上述性质后我们可以设置四个边界变量，然后按填数顺序不断填数即可，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        L, R, U, D = 0, n - 1, 0, n - 1
        ans = [[0 for i in range(n)] for i in range(n)]
        num, cnt = 1, n * n
        while num <= cnt:
            for i in range(L, R + 1):
                ans[U][i] = num
                num += 1
            U += 1
            for i in range(U, D + 1):
                ans[i][R] = num
                num += 1
            R -= 1
            for i in range(R, L - 1, -1):
                ans[D][i] = num
                num += 1
            D -= 1
            for i in range(D, U - 1, -1):
                ans[i][L] = num
                num += 1
            L += 1
        return ans

发表于 分类于 Valine：

题目链接

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

在这里插入图片描述

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

在这里插入图片描述

1
2
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

找规律~
拿样例来说明，对样例一：

1
2
3
4
5
6
7
8
9
10
11
12
13
1 2 3
4 5 6
7 8 9
我们先拿出第一个列表元素 [1,2,3]
此时矩阵为 [[4,5,6],[7,8,9]]
我们从矩阵的每一列表元素里各取一个元素组成新矩阵 [[4,7],[5,8],[6,9]]
再倒置，得到 [[6,9],[5,8],[4,7]]
再拿出第一个列表元素 [6,9]
此时矩阵为 [[5,8],[4,7]]
从矩阵的每一列表元素里各取一个元素组成新矩阵 [[5,4],[8,7]]
再倒置，得到 [[8,7],[5,4]]
再拿出第一个列表元素...
直至矩阵为空

对样例二我们发现也是重复上述过程，这个规律的关键就是 从矩阵的每一列表元素里各取一个元素组成新矩阵，而 Python 中恰有这样的一个函数 zip，AC 代码如下：

1
2
3
4
5
6
7
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res += matrix.pop(0)
            matrix = list(zip(*matrix))[::-1]
        return res

发表于 分类于 Valine：

题目链接

外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。

字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：

单词 word 中包含谜面 puzzle 的第一个字母。
单词 word 中的每一个字母都可以在谜面 puzzle 中找到。
例如，如果字谜的谜面是 “abcdefg”，那么可以作为谜底的单词有 “faced”, “cabbage”, 和 “baggage”；而 “beefed”（不含字母 “a”）以及 “based”（其中的 “s” 没有出现在谜面中）都不能作为谜底。
返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。

示例：

1
2
3
4
5
6
7
8
9
10
11
输入：
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
输出：[1,1,3,2,4,0]
解释：
1 个单词可以作为 "aboveyz" 的谜底 : "aaaa" 
1 个单词可以作为 "abrodyz" 的谜底 : "aaaa"
3 个单词可以作为 "abslute" 的谜底 : "aaaa", "asas", "able"
2 个单词可以作为 "absoryz" 的谜底 : "aaaa", "asas"
4 个单词可以作为 "actresz" 的谜底 : "aaaa", "asas", "actt", "access"
没有单词可以作为 "gaswxyz" 的谜底，因为列表中的单词都不含字母 'g'。

位运算+暴力~
如果完全采用暴力的方法，光遍历一遍的复杂度就已经达到 $1e9$，所以我们必须要先存储每个单词的状态，有以下两种方法：

  • set存储
  • 通过位运算字符串转换成数字存储

第一种方法操作比较简单，但是实操超时了；第二种方法比较难想，我们可以用一个 $26$ 位的二进制数表示一个单词，然后用 $map$ 记录每个二进制数的个数；谜面由于只有 $7$ 位，所以可以暴力算出谜面的所有子集可能，依次加入答案即可，AC代码如下：

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
class Solution {
public:
    vector<int> findNumOfValidWords(vector<string> &words, vector<string> &puzzles) {
        unordered_map<int, int> mp;
        vector<int> ans;
        for (auto &i:words) {
            int num = 0;
            for (auto &j:i) {
                num |= (1 << (j - 'a'));
            }
            mp[num]++;
        }
        for (auto &i:puzzles) {
            int n = i.size(), sum = 0;
            for (int j = 0; j < (1 << (n - 1)); j++) {
                int num = 0;
                num |= (1 << (i.front() - 'a'));
                for (int k = 0; k < n - 1; k++) if ((1 << k) & j) num |= (1 << (i[k + 1] - 'a'));
                sum += mp[num];
            }
            ans.emplace_back(sum);
        }
        return ans;
    }
};

发表于 分类于 Valine：

题目链接

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串是正着读和反着读都一样的字符串。

示例 1：

1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

1
2
输入：s = "a"
输出：[["a"]]

暴力所有分隔符，显然对一个长为 $n$ 的字符串最多可以划分成 $n$ 个子串，那么我们就可以暴力所有的可能，复杂度 $O(2^n)$~
注意最后一个位置必须要切，拿样例 1 举例：

1
2
3
4
5
aab
1: aab|
2: ab|b|
3: a|ab|
4: a|a|b|

还有一个细节，因为位数固定了，但是小数的二进制位数比大数小，所以小数的二进制数要在前面补 0，AC代码如下：

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
37
38
class Solution {
public:
    bool check(string s) {
        string ss = s;
        reverse(s.begin(), s.end());
        return s == ss;
    }

    vector<vector<string>> partition(string s) {
        int n = s.size();
        if (n == 1) return {{s}};
        else {
            vector<vector<string>> ans;
            for (int i = 0; i < (1 << (n - 1)); i++) {
                int pos = 0, flag = 1;
                vector<string> v;
                string div = "";
                int num = i;
                while (num) {
                    div = to_string(num % 2) + div;
                    num /= 2;
                }
                while (div.size() < n - 1) div = '0' + div;
                div += '1';
                for (int j = 0; j < n; j++) {
                    if (div[j] == '1') {
                        string ss = s.substr(pos, j - pos + 1);
                        v.emplace_back(ss);
                        if (!check(ss)) flag = 0;
                        pos = j + 1;
                    }
                }
                if (flag) ans.emplace_back(v);
            }
            return ans;
        }
    }
};

发表于 分类于 Valine：

题目链接

今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。

在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。

请你返回这一天营业下来，最多有多少客户能够感到满意的数量。

示例：

1
2
3
4
5
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出：16
解释：
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

前缀和~
记录不算老板情绪的前缀和 $sum1$ 和算老板情绪的前缀和 $sum2$，遍历 $i\in[0,n-X]$，显然对每个 $i$，答案就是 $sum2.back()+sum1[i+X-1]-sum1[i-1]-(sum2[i+X-1]-sum2[i-1])$，这个公式计算的就是此位置往后连续 $X$ 分钟老板的情绪都不生气后增加的满意顾客数量，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxSatisfied(vector<int> &customers, vector<int> &grumpy, int X) {
        vector<int> sum1, sum2;
        int n = customers.size(), ans = 0;
        for (int i = 0; i < n; i++) {
            if (sum1.empty()) sum1.emplace_back(customers[i]);
            else sum1.emplace_back(sum1.back() + customers[i]);
            if (sum2.empty()) sum2.emplace_back(grumpy[i] ? 0 : customers[i]);
            else sum2.emplace_back(sum2.back() + (grumpy[i] ? 0 : customers[i]));
        }
        for (int i = 0; i <= n - X; i++){
            ans = max(ans, sum2.back() + sum1[i + X - 1] - (i ? sum1[i - 1] : 0) - (sum2[i + X - 1] - (i ? sum2[i - 1] : 0)));
        }
        return ans;
    }
};

发表于 分类于 Valine：

题目链接

你打算做甜点，现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。而制作甜点需要遵循以下几条规则：

  • 必须选择 一种 冰激凌基料。
  • 可以添加 一种或多种 配料，也可以不添加任何配料。
  • 每种类型的配料最多两份 。

给你以下三个输入：

  • baseCosts ，一个长度为 n 的整数数组，其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。
  • toppingCosts，一个长度为 m 的整数数组，其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。
  • target ，一个整数，表示你制作甜点的目标价格。
    你希望自己做的甜点总成本尽可能接近目标价格 target 。

返回最接近 target 的甜点成本。如果有多种方案，返回 成本相对较低 的一种。

示例 1：

1
2
3
4
5
6
7
输入：baseCosts = [1,7], toppingCosts = [3,4], target = 10
输出：10
解释：考虑下面的方案组合（所有下标均从 0 开始）：
- 选择 1 号基料：成本 7
- 选择 1 份 0 号配料：成本 1 x 3 = 3
- 选择 0 份 1 号配料：成本 0 x 4 = 0
总成本：7 + 3 + 0 = 10 。

示例 2：

1
2
3
4
5
6
7
8
输入：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
输出：17
解释：考虑下面的方案组合（所有下标均从 0 开始）：
- 选择 1 号基料：成本 3
- 选择 1 份 0 号配料：成本 1 x 4 = 4
- 选择 2 份 1 号配料：成本 2 x 5 = 10
- 选择 0 份 2 号配料：成本 0 x 100 = 0
总成本：3 + 4 + 10 + 0 = 17 。不存在总成本为 18 的甜点制作方案。

示例 3：

1
2
3
输入：baseCosts = [3,10], toppingCosts = [2,5], target = 9
输出：8
解释：可以制作总成本为 8 和 10 的甜点。返回 8 ，因为这是成本更低的方案。

示例 4：

1
2
3
输入：baseCosts = [10], toppingCosts = [1], target = 1
输出：10
解释：注意，你可以选择不添加任何配料，但你必须选择一种基料。

看一下 n,m 的范围很容易发现就是暴力，复杂度 $O(n*3^m)$，对每种配料考虑不选，选一份，选两份这三种情况即可~
DFS 的过程中记录最小答案，AC代码如下：

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
class Solution {
private:
    int mn = 1e9, ans = 1e9;
public:
    void dfs(vector<int> &a, int id, int sum, int m, int res, int base) {
        if (id == m) {
            if (abs(sum - res) < mn) {
                mn = abs(sum - res);
                ans = sum + base;
            } else if (abs(sum - res) == mn) {
                ans = min(ans, sum + base);
            }
            return;
        }
        dfs(a, id + 1, sum, m, res, base);
        dfs(a, id + 1, sum + a[id], m, res, base);
        dfs(a, id + 1, sum + 2 * a[id], m, res, base);
    }

    int closestCost(vector<int> &baseCosts, vector<int> &toppingCosts, int target) {
        int m = toppingCosts.size();
        for (auto i:baseCosts) {
            int res = target - i;
            dfs(toppingCosts, 0, 0, m, res, i);
        }
        return ans;
    }
};

发表于 分类于 Valine：

题目链接

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

示例 1:

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

单调栈~

栈内存元素下标，栈顶放最小值，对当前的 nums[i]，若栈顶元素 nums[st.top()]<nums[i]，证明 nums[i] 就是栈顶元素的下一个更大元素，直接存入答案就行~
题目另外要求可以循环遍历，我们可以采用取模操作进行优化，AC代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> nextGreaterElements(vector<int> &nums) {
        int n = nums.size();
        vector<int> ans(n, -1);
        stack<int> st;
        for (int i = 0; i < 2 * n - 1; i++) {
            while (!st.empty() && nums[st.top()] < nums[i % n]) {
                ans[st.top()] = nums[i % n];
                st.pop();
            }
            st.push(i % n);
        }
        return ans;
    }
};