单调栈.md 23.0 KB
Newer Older
L
labuladong 已提交
1 2
# 特殊数据结构:单调栈

L
labuladong 已提交
3 4 5 6 7 8






L
labuladong 已提交
9 10


11 12
<p align='center'>
<a href="https://github.com/labuladong/fucking-algorithm" target="view_window"><img alt="GitHub" src="https://img.shields.io/github/stars/labuladong/fucking-algorithm?label=Stars&style=flat-square&logo=GitHub"></a>
L
labuladong 已提交
13
<a href="https://appktavsiei5995.pc.xiaoe-tech.com/index" target="_blank"><img class="my_header_icon" src="https://img.shields.io/static/v1?label=精品课程&message=查看&color=pink&style=flat"></a>
14 15 16 17
<a href="https://www.zhihu.com/people/labuladong"><img src="https://img.shields.io/badge/%E7%9F%A5%E4%B9%8E-@labuladong-000000.svg?style=flat-square&logo=Zhihu"></a>
<a href="https://space.bilibili.com/14089380"><img src="https://img.shields.io/badge/B站-@labuladong-000000.svg?style=flat-square&logo=Bilibili"></a>
</p>

L
labuladong 已提交
18
![](https://labuladong.github.io/algo/images/souyisou1.png)
19

L
labuladong 已提交
20
**通知:[数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO) 已更新到 V2.0,第 12 期刷题打卡 [开始报名](https://aep.xet.tech/s/XhcRc),点击这里体验 [刷题全家桶](https://labuladong.gitee.io/algo/images/others/%E5%85%A8%E5%AE%B6%E6%A1%B6.jpg)。**
21 22 23



L
labuladong 已提交
24
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
25

L
labuladong 已提交
26 27 28 29 30
| LeetCode | 力扣 | 难度 |
| :----: | :----: | :----: |
| [496. Next Greater Element I](https://leetcode.com/problems/next-greater-element-i/) | [496. 下一个更大元素 I](https://leetcode.cn/problems/next-greater-element-i/) | 🟢
| [503. Next Greater Element II](https://leetcode.com/problems/next-greater-element-ii/) | [503. 下一个更大元素 II](https://leetcode.cn/problems/next-greater-element-ii/) | 🟠
| [739. Daily Temperatures](https://leetcode.com/problems/daily-temperatures/) | [739. 每日温度](https://leetcode.cn/problems/daily-temperatures/) | 🟠
31 32

**-----------**
L
labuladong 已提交
33

L
labuladong 已提交
34
栈(stack)是很简单的一种数据结构,先进后出的逻辑顺序,符合某些问题的特点,比如说函数调用栈。单调栈实际上就是栈,只是利用了一些巧妙的逻辑,使得每次新元素入栈后,栈内的元素都保持有序(单调递增或单调递减)。
L
labuladong 已提交
35

L
labuladong 已提交
36
听起来有点像堆(heap)?不是的,单调栈用途不太广泛,只处理一类典型的问题,比如「下一个更大元素」,「上一个更小元素」等。本文用讲解单调队列的算法模版解决「下一个更大元素」相关问题,并且探讨处理「循环数组」的策略。至于其他的变体和经典例题,我会在 [数据结构精品课](https://aep.h5.xeknow.com/s/1XJHEO) 中讲解。
L
labuladong 已提交
37

38 39
### 单调栈模板

L
labuladong 已提交
40
现在给你出这么一道题:输入一个数组 `nums`,请你返回一个等长的结果数组,结果数组中对应索引存储着下一个更大元素,如果没有更大的元素,就存 -1。函数签名如下:
41

L
labuladong 已提交
42 43
```java
int[] nextGreaterElement(int[] nums);
44
```
L
labuladong 已提交
45

L
labuladong 已提交
46
比如说,输入一个数组 `nums = [2,1,2,4,3]`,你返回数组 `[4,2,4,-1,-1]`。因为第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2;第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数,填 -1;3 后面没有比 3 大的数,填 -1。
L
labuladong 已提交
47

48
这道题的暴力解法很好想到,就是对每个元素后面都进行扫描,找到第一个更大的元素就行了。但是暴力解法的时间复杂度是 `O(n^2)`
L
labuladong 已提交
49

L
labuladong 已提交
50
这个问题可以这样抽象思考:把数组的元素想象成并列站立的人,元素大小想象成人的身高。这些人面对你站成一列,如何求元素「2」的下一个更大元素呢?很简单,如果能够看到元素「2」,那么他后面可见的第一个人就是「2」的下一个更大元素,因为比「2」小的元素身高不够,都被「2」挡住了,第一个露出来的就是答案。
L
labuladong 已提交
51

L
labuladong 已提交
52
![](https://labuladong.github.io/algo/images/单调栈/1.jpeg)
L
labuladong 已提交
53 54 55

这个情景很好理解吧?带着这个抽象的情景,先来看下代码。

L
labuladong 已提交
56 57 58 59 60 61
```java
int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    // 存放答案的数组
    int[] res = new int[n];
    Stack<Integer> s = new Stack<>(); 
62
    // 倒着往栈里放
L
labuladong 已提交
63
    for (int i = n - 1; i >= 0; i--) {
64
        // 判定个子高矮
L
labuladong 已提交
65
        while (!s.isEmpty() && s.peek() <= nums[i]) {
66 67
            // 矮个起开,反正也被挡着了。。。
            s.pop();
L
labuladong 已提交
68
        }
L
labuladong 已提交
69 70
        // nums[i] 身后的更大元素
        res[i] = s.isEmpty() ? -1 : s.peek();
71
        s.push(nums[i]);
L
labuladong 已提交
72
    }
73
    return res;
L
labuladong 已提交
74 75 76
}
```

L
labuladong 已提交
77
这就是单调队列解决问题的模板。for 循环要从后往前扫描元素,因为我们借助的是栈的结构,倒着入栈,其实是正着出栈。while 循环是把两个「个子高」元素之间的元素排除,因为他们的存在没有意义,前面挡着个「更高」的元素,所以他们不可能被作为后续进来的元素的下一个更大元素了。
78 79

这个算法的时间复杂度不是那么直观,如果你看到 for 循环嵌套 while 循环,可能认为这个算法的复杂度也是 `O(n^2)`,但是实际上这个算法的复杂度只有 `O(n)`
L
labuladong 已提交
80

81
分析它的时间复杂度,要从整体来看:总共有 `n` 个元素,每个元素都被 `push` 入栈了一次,而最多会被 `pop` 一次,没有任何冗余操作。所以总的计算规模是和元素规模 `n` 成正比的,也就是 `O(n)` 的复杂度。
L
labuladong 已提交
82

83
### 问题变形
L
labuladong 已提交
84

L
labuladong 已提交
85 86 87 88 89 90 91 92 93
单调栈的使用技巧差不多了,首先来一个简单的变形,力扣第 496 题「下一个更大元素 I」:

![](https://labuladong.github.io/algo/images/单调栈/title.jpg)

这道题给你输入两个数组 `nums1``nums2`,让你求 `nums1` 中的元素在 `nums2` 中的下一个更大元素,函数签名如下:

```java
int[] nextGreaterElement(int[] nums1, int[] nums2)
```
L
labuladong 已提交
94

L
labuladong 已提交
95
其实和把我们刚才的代码改一改就可以解决这道题了,因为题目说 `nums1``nums2` 的子集,那么我们先把 `nums2` 中每个元素的下一个更大元素算出来存到一个映射里,然后再让 `nums1` 中的元素去查表即可:
96

L
labuladong 已提交
97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
```java
int[] nextGreaterElement(int[] nums1, int[] nums2) {
    // 记录 nums2 中每个元素的下一个更大元素
    int[] greater = nextGreaterElement(nums2);
    // 转化成映射:元素 x -> x 的下一个最大元素
    HashMap<Integer, Integer> greaterMap = new HashMap<>();
    for (int i = 0; i < nums2.length; i++) {
        greaterMap.put(nums2[i], greater[i]);
    }
    // nums1 是 nums2 的子集,所以根据 greaterMap 可以得到结果
    int[] res = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        res[i] = greaterMap.get(nums1[i]);
    }
    return res;
}
113

L
labuladong 已提交
114 115 116
int[] nextGreaterElement(int[] nums) {
    // 见上文
}
117
```
L
labuladong 已提交
118 119


L
labuladong 已提交
120 121 122
再看看力扣第 739 题「每日温度」:

给你一个数组 `temperatures`,这个数组存放的是近几天的天气气温,你返回一个等长的数组,计算:对于每一天,你还要至少等多少天才能等到一个更暖和的气温;如果等不到那一天,填 0。函数签名如下:
L
labuladong 已提交
123

L
labuladong 已提交
124 125 126 127 128 129 130
```java
int[] dailyTemperatures(int[] temperatures);
```

比如说给你输入 `temperatures = [73,74,75,71,69,76]`,你返回 `[1,1,3,2,1,0]`。因为第一天 73 华氏度,第二天 74 华氏度,比 73 大,所以对于第一天,只要等一天就能等到一个更暖和的气温,后面的同理。

这个问题本质上也是找下一个更大元素,只不过现在不是问你下一个更大元素的值是多少,而是问你当前元素距离下一个更大元素的索引距离而已。
L
labuladong 已提交
131

132
相同的思路,直接调用单调栈的算法模板,稍作改动就可以,直接上代码吧:
L
labuladong 已提交
133

L
labuladong 已提交
134 135 136 137
```java
int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] res = new int[n];
138
    // 这里放元素索引,而不是元素
L
labuladong 已提交
139
    Stack<Integer> s = new Stack<>(); 
140
    /* 单调栈模板 */
L
labuladong 已提交
141 142
    for (int i = n - 1; i >= 0; i--) {
        while (!s.isEmpty() && temperatures[s.peek()] <= temperatures[i]) {
L
labuladong 已提交
143 144
            s.pop();
        }
145
        // 得到索引间距
L
labuladong 已提交
146
        res[i] = s.isEmpty() ? 0 : (s.peek() - i); 
147 148
        // 将索引入栈,而不是元素
        s.push(i); 
L
labuladong 已提交
149
    }
150
    return res;
L
labuladong 已提交
151 152 153
}
```

154
单调栈讲解完毕,下面开始另一个重点:如何处理「循环数组」。
L
labuladong 已提交
155

156
### 如何处理环形数组
L
labuladong 已提交
157

L
labuladong 已提交
158
同样是求下一个更大元素,现在假设给你的数组是个环形的,如何处理?力扣第 503 题「下一个更大元素 II」就是这个问题:输入一个「环形数组」,请你计算其中每个元素的下一个更大元素。
L
labuladong 已提交
159

L
labuladong 已提交
160
比如输入 `[2,1,2,4,3]`,你应该返回 `[4,2,4,-1,4]`,因为拥有了环形属性,**最后一个元素 3 绕了一圈后找到了比自己大的元素 4**
L
labuladong 已提交
161

L
labuladong 已提交
162
我们一般是通过 % 运算符求模(余数),来模拟环形特效:
L
labuladong 已提交
163 164 165 166 167

```java
int[] arr = {1,2,3,4,5};
int n = arr.length, index = 0;
while (true) {
L
labuladong 已提交
168
    // 在环形数组中转圈
L
labuladong 已提交
169 170 171 172 173
    print(arr[index % n]);
    index++;
}
```

L
labuladong 已提交
174
这个问题肯定还是要用单调栈的解题模板,但难点在于,比如输入是 `[2,1,2,4,3]`,对于最后一个元素 3,如何找到元素 4 作为下一个更大元素。
175 176 177

**对于这种需求,常用套路就是将数组长度翻倍**

L
labuladong 已提交
178
![](https://labuladong.github.io/algo/images/单调栈/2.jpeg)
L
labuladong 已提交
179

L
labuladong 已提交
180
这样,元素 3 就可以找到元素 4 作为下一个更大元素了,而且其他的元素都可以被正确地计算。
L
labuladong 已提交
181

L
labuladong 已提交
182
有了思路,最简单的实现方式当然可以把这个双倍长度的数组构造出来,然后套用算法模板。但是,**我们可以不用构造新数组,而是利用循环数组的技巧来模拟数组长度翻倍的效果**。直接看代码吧:
L
labuladong 已提交
183

L
labuladong 已提交
184 185 186 187 188 189
```java
int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Stack<Integer> s = new Stack<>();
    // 数组长度加倍模拟环形数组
L
labuladong 已提交
190
    for (int i = 2 * n - 1; i >= 0; i--) {
L
labuladong 已提交
191 192
        // 索引 i 要求模,其他的和模板一样
        while (!s.isEmpty() && s.peek() <= nums[i % n]) {
L
labuladong 已提交
193
            s.pop();
L
labuladong 已提交
194 195
        }
        res[i % n] = s.isEmpty() ? -1 : s.peek();
L
labuladong 已提交
196 197 198 199 200 201
        s.push(nums[i % n]);
    }
    return res;
}
```

202
这样,就可以巧妙解决环形数组的问题,时间复杂度 `O(N)`
L
labuladong 已提交
203

L
labuladong 已提交
204 205
最后提出一些问题吧,本文提供的单调栈模板是 `nextGreaterElement` 函数,可以计算每个元素的下一个更大元素,但如果题目让你计算上一个更大元素,或者计算上一个更大或相等的元素,应该如何修改对应的模板呢?而且在实际应用中,题目不会直接让你计算下一个(上一个)更大(小)的元素,你如何把问题转化成单调栈相关的问题呢?

L
labuladong 已提交
206
我会在 [单调栈的几种变体](https://appktavsiei5995.pc.xiaoe-tech.com/detail/i_628dc1ace4b09dda126cf793/1) 对比单调栈的几种其他形式,并在 [单调栈的运用](https://appktavsiei5995.pc.xiaoe-tech.com/detail/i_628dc2d7e4b0cedf38b67734/1) 中给出单调栈的经典例题。更多数据结构设计类题目参见 [数据结构设计经典习题](https://appktavsiei5995.pc.xiaoe-tech.com/detail/i_6312b9e5e4b0eca59c2b7e93/1)
L
labuladong 已提交
207

208
**_____________**
L
labuladong 已提交
209

L
labuladong 已提交
210
**《labuladong 的算法小抄》已经出版,关注公众号查看详情;后台回复关键词「**进群**」可加入算法群;回复「**全家桶**」可下载配套 PDF 和刷题全家桶**
L
labuladong 已提交
211

L
labuladong 已提交
212
![](https://labuladong.github.io/algo/images/souyisou2.png)
L
labuladong 已提交
213

J
JiangangZhao 已提交
214 215
======其他语言代码======

B
brucecat 已提交
216 217 218 219 220 221 222 223
[496.下一个更大元素I](https://leetcode-cn.com/problems/next-greater-element-i)

[503.下一个更大元素II](https://leetcode-cn.com/problems/next-greater-element-ii)

[739.每日温度](https://leetcode-cn.com/problems/daily-temperatures/)



224 225
### java

Z
zak 已提交
226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277
[ZakAnun](https://github.com/ZakAnun) 提供代码

```java
// 496.下一个更大元素
// 暴力解法
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    int[] result = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        // 需要记录第一个数组每个元素在第二个数组中出现的位置
        int index = 0;
        for (int j = 0; j < nums2.length; j++) {
            if (nums1[i] == nums2[j]) {
                index = j;
                break;
            }
        }
        // 根据找到的位置往后遍历,若符合条件则记录到结果数组
        for (int k = index; k < nums2.length; k++) {
            if (nums2[k] > nums1[i]) {
                result[i] = nums2[k];
                break;
            }
        }
        // 判断若对应位置结果依然为默认值,则将其修改为 -1
        if (result[i] == 0) {
            result[i] = -1;
        }
    }
    return result;
}

// 分析: 暴力解法中需要确定数组1中每个元素在数组2中的下标而需要进行额外的遍历导致时间复杂度升高,
// 但若能够先罗列出全部的结果,然后从结果集中获取数组1中每个元素对应的下一个更大元素,就可以节省这部分时间(这里需要引用 HashMap 帮助我们记录结果,以便根据数组1获取。
// 单调栈解法
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Stack<Integer> stack = new Stack <>();
    HashMap<Integer, Integer> map = new HashMap <>();
    int[] result = new int[nums1.length];
    for (int value : nums2) {
        while (!stack.empty() && value > stack.peek()) {
            map.put(stack.pop(), value);
        }
        stack.push(value);
    }
    while (!stack.empty()) {
        map.put(stack.pop(), -1);
    }
    for (int i = 0; i < nums1.length; i++) {
        result[i] = map.get(nums1[i]);
    }
    return result;
}
B
BruceCat 已提交
278 279
```

B
BruceCat 已提交
280
[ZakAnun](https://github.com/ZakAnun) 提供代码
B
BruceCat 已提交
281

282
```java
R
Rui Yang 已提交
283 284 285 286 287 288
// 739. Daily Temperatures
class Solution {
    public int[] dailyTemperatures(int[] T) {
        Stack<Integer> stack = new Stack<>();
        int[] ans = new int[T.length];
        for (int i = 0; i < T.length; i++) {
R
Rui Yang 已提交
289
            // 如果压栈之后不满足单调递减,弹出元素,直至保持单调性
R
Rui Yang 已提交
290 291
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int index = stack.pop();
R
Rui Yang 已提交
292
                // 被弹出的元素(T[index])都是小于当前的元素(T[i]),由于栈内元素单调递减,大于被弹出元素(index)的最近的就是当前元素(i)
R
Rui Yang 已提交
293 294 295 296 297 298 299
                ans[index] = i - index;
            }
            stack.push(i);
        }
        return ans;
    }
}
B
BruceCat 已提交
300 301 302 303
```

[JiangangZhao](https://github.com/JiangangZhao)提供【503.下一个更大元素II】【java】

J
JiangangZhao 已提交
304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334
```java
class Solution {
    public int[] nextGreaterElements(int[] nums) {
        //数组长度
        int n = nums.length;
        //逻辑拼接,数组长度翻倍
        int len = n*2 - 1;
        //存储结果数组
        int[] res = new int[n];
        //存放索引,不是元素
        LinkedList<Integer> s = new LinkedList<>();
        //从前往后遍历
        for (int i = 0; i < len; ++i) {
            //索引要取模
            int val = nums[i % n];
            //当前元素比栈顶元素大,即是栈顶元素的下一个更大的元素
            while (!s.isEmpty() && val > nums[s.peek()]) {
                res[s.pop()] = val;
            }
            //i<n时入栈
            if (i < n) {
                s.push(i);
            }
        }
        //栈中剩余的索引不存在下一个更大的元素,赋值-1
        while (!s.isEmpty()) {
            res[s.pop()] = -1;
        }
        return res;
    }
}
B
brucecat 已提交
335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631
```



### javascript

单调栈模板

[496.下一个更大元素I](https://leetcode-cn.com/problems/next-greater-element-i)

这里需要用一个map记录nums2中各项的下一个更大值,为何?注意读题。

- nums1和nums2中所有整数 互不相同
- nums1 中的所有整数同样出现在 nums2 中

如果还是用数组的话,num1中元素在nums2中的位置并不好找,所以这里使用map来维护。

其它核心思想和上文中的大抵相同。值得注意的是,入栈顺序可以有正着入栈和倒着入栈,顺序不同,维护的动作也不同,详见下文。

正着入栈如下。

```js
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function (nums1, nums2) {
    let len1 = nums1.length;
    let len2 = nums2.length;

    // base case
    if (len1 < 1 || len2 < 1 || len1 > len2) {
        return [];
    }

    let res = new Array(len1); // 存放答案的数组
    let stack = [];
    let map = {};

    // 启动条件
    stack.push(nums2[0]);

    // 右边数字入栈
    for (let j = 1; j < len2; j++) {
        let currNum = nums2[j];

        // 单调栈栈顶元素和当前数组元素作比较
        // 找到下一个更大元素
        while (stack.length !== 0 && currNum > stack[stack.length - 1]) {
            map[stack.pop()] = currNum;
        }

        stack.push(currNum);
    }

    // 栈不为空 这些元素都是找不到下一个更大值的
    while (stack.length !== 0) {
        map[stack.pop()] = -1;
    }

    for (let i = 0; i < len1; i++) {
        res[i] = map[nums1[i]];
    }
    return res;

};
```



接下来是倒着入栈,就是上文中提到的排队思路。

抽象思路,nums2看做排队找后面第一个比自己高的高个子。

```js
var nextGreaterElement = function(nums1, nums2) {
    // 把此类问题比作排队看后面第一个比自己高的
    // 从后面开始遍历往前面看,就能很好的避免不知道后面什么情况了
    let stack = []
    let res = []
    let map = new Map()
    for(let i = nums2.length - 1; i >= 0; i--){
        // 矮个子起开,要你也没用,反正看不见你
        while(stack.length && nums2[i] >= stack[stack.length - 1]){
            stack.pop()
        }
        //有比我个子高的吗?有就是你了,没有就是-1
        map.set(nums2[i], stack.length ? stack[stack.length - 1] : -1)
        stack.push(nums2[i])
    }

    nums1.forEach(item => {
        res.push(map.get(item))
    })
    return res;
};

```

解决了这道题,后面的题就很容易理解了。在这道题的基础上,让单调栈中存放的元素是下标而不是值,因为有的题目需要根据下标计算,这样泛化性更好。

正着入栈,存储下标。

```js
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function (nums1, nums2) {
    let len1 = nums1.length;
    let len2 = nums2.length;

    // base case
    if (len1 < 1 || len2 < 1 || len1 > len2) {
        return [];
    }

    let map = new Map()
    let res = [];  // 存放结果
    let stack = []
    for (let i = 0; i < len2; i++) {
        //栈顶元素存在,并且当前的元素大于栈顶
        while (stack.length && nums2[i] > nums2[stack[stack.length - 1]]) {
            // 关键步骤1
            let index = stack.pop();
            map.set(nums2[index], nums2[i])
        }

        // 关键步骤2 下标入栈
        stack.push(i)
    }

    //栈内还有元素,说明后面没有比自己小的了
    while (stack.length) {
        let index = stack.pop();
        map.set(nums2[index], -1)
    }

    // 最后导出结果
    nums1.forEach(item => {
        res.push(map.get(item))
    })
    return res
};
```

倒着入栈,存储下标。

```js
// 存储的是下标
var nextGreaterElement = function (nums1, nums2) {
    // 把此类问题比作排队看后面第一个比自己高的
    // 从后面开始遍历往前面看,就能很好的避免不知道后面什么情况了
    let stack = []
    let res = []
    let map = new Map()

    for (let i = nums2.length - 1; i >= 0; i--) {
        // 矮个子起开,要你也没用,反正看不见你
        while (stack.length && nums2[i] >= nums2[stack[stack.length - 1]]) {
            stack.pop()
        }
        
        //有比我个子高的吗?有就是你了,没有就是-1
        map.set(nums2[i], stack.length ? nums2[stack[stack.length - 1]] : -1)

        // 关键步骤:存储的是下标
        stack.push(i)
    }

    nums1.forEach(item => {
        res.push(map.get(item))
    })
    return res;
};

```

进一步而谈,其实map也可以转化成使用index对应index,不过这种情况的题比较少见,了解即可,不必抛开框架深入追究细节。

```js
nums1:[4,1,2]
nums2:[1,3,4,2]

直接num1的value对nums2的value 前提value唯一
{
	4: -1
  1: 3
  2: -1
}

num1的index对nums2的index
这里也可以用数组来做自由发挥吧,这里只提供一些思路
{
  0-1
  11
  2-1
}
```



**[503.下一个更大元素II](https://leetcode-cn.com/problems/next-greater-element-ii)**

因为是环形数组,所以最后一个数的下一个最大的数不是-1,而是要把再数组从头开始遍历到末尾得出这个数,可以把数组扩大两倍解决。

- 把数组扩大两倍逆序遍历依次放入栈中,栈中的栈顶元素代表下一个迭代的数的后面第一个最大的数;
- 当前数比栈顶元素大时,出栈;
- 此时栈有值时,栈顶元素即为当前数的下一个最大的数,把它存入结果数组对应的下标中;
- 把当前数入栈

这里用的和上文一样,还是反着入栈,相信读者可以自己悟出正着入栈怎么写了吧。

```js
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var nextGreaterElements = function (nums) {
    let n = nums.length;
    let res = [];

    let stack = [];

    // 假装这个数组长度翻倍了
    for (let i = 2 * n - 1; i >= 0; i--) {
        // 索引要求模,其他的和模板一样
        while (stack.length && stack[stack.length - 1] <= nums[i % n])
            stack.pop();
        res[i % n] = stack.length ? stack[stack.length - 1] : -1;
        stack.push(nums[i % n]);
    }
    return res;
};
```



**[739.每日温度](https://leetcode-cn.com/problems/daily-temperatures/)**

很简单,就是第一个next greater的变形而已,存储的是索引。

倒着入栈。

```js
/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function (T) {
    let res = new Array(T.length).fill(0);


    // 这里放元素索引,而不是元素
    let stack = [];

    /* 单调栈模板 */
    for (let i = T.length - 1; i >= 0; i--) {
        while (stack.length !== 0 && T[stack[stack.length - 1]] <= T[i]) {
            stack.pop();
        }
        // 得到索引间距
        res[i] = stack.length === 0 ? 0 : (stack[stack.length - 1] - i);

        // 将索引入栈,而不是元素
        stack.push(i);
    }
    return res;
};
```

正着入栈,es6写法。

```js
const dailyTemperatures = (T) => {
    const res = new Array(T.length).fill(0);
    for (let i = 0; i < T.length; i++) {
        for (let j = i + 1; j < T.length; j++) {
            if (T[j] > T[i]) {
                res[i] = j - i;
                break;
            }
        }
    }
    return res;
}
```

部分做题规律如下,仅供做题套路参考,实际可以自由发挥。

当前项向左找第一个比自己大的位置:从左向右维护一个单调递减栈
当前项向左找第一个比自己小的位置:从左向右维护一个单调递增栈
当前项向右找第一个比自己大的位置:从右向左维护一个单调递减栈
当前项向右找第一个比自己小的位置:从右向左维护一个单调递增栈