-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathleetcode-stacks&queues.html
723 lines (719 loc) · 238 KB
/
leetcode-stacks&queues.html
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
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
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
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
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
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
<!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=2"><meta name="theme-color" content="#222"><meta http-equiv="X-UA-COMPATIBLE" content="IE=edge,chrome=1"><meta name="renderer" content="webkit"><link rel="icon" type="image/ico" sizes="32x32" href="/assets/favicon.ico"><link rel="apple-touch-icon" sizes="180x180" href="/assets/apple-touch-icon.png"><link rel="alternate" href="/rss.xml" title="Jiankychen's Blog" type="application/rss+xml"><link rel="alternate" href="/atom.xml" title="Jiankychen's Blog" type="application/atom+xml"><link rel="alternate" type="application/json" title="Jiankychen's Blog" href="https://jiankychen.github.io/feed.json"><link rel="preconnect" href="https://lf9-cdn-tos.bytecdntp.com"><link rel="preconnect" href="https://at.alicdn.com"><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Mulish:400,400italic,700,700italic%7CFredericka%20the%20Great:400,400italic,700,700italic%7CNoto%20Serif%20JP:400,400italic,700,700italic%7CNoto%20Serif%20SC:400,400italic,700,700italic%7CInconsolata:400,400italic,700,700italic&display=swap&subset=latin,latin-ext" media="none" onload="this.media='all'"><link rel="stylesheet" href="/css/app.css?v=0.4.2"><link rel="modulepreload" href="/js/chunk-7IVLRIQ3.js"><link rel="modulepreload" href="/js/chunk-IXT6LZJL.js"><link rel="modulepreload" href="/js/chunk-PHSEV26P.js"><link rel="modulepreload" href="/js/chunk-XHQGHZCW.js"><link rel="modulepreload" href="/js/comments-TUWNDU5I.js"><link rel="modulepreload" href="/js/post-P6IN2S3Y.js"><link rel="modulepreload" href="/js/quicklink-HAJEHOPK.js"><link rel="modulepreload" href="/js/search-WFXK2K66.js"><link rel="modulepreload" href="/js/siteInit.js"><link rel="stylesheet" href="https://npm.webcache.cn/@waline/[email protected]/dist/waline.css" media="none" onload="this.media='all'"><link rel="preload" href="https://i.imgtg.com/2023/03/09/Y0hOs.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/8fe50780c15461b629c9aeab5a7f2acd.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/Y0iNK.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/99fb5ff897a82984470abf5e2a235d94.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/9b626c5ba21d7cb4dbcba2b507688bbb.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/2aabaeb8aca379b991071d1c41632741.jpg" as="image" fetchpriority="high"><meta name="keywords" content="队列,"><link rel="canonical" href="https://jiankychen.github.io/leetcode-stacks&queues"><title>LeetCode - 栈与队列专题</title><meta name="generator" content="Hexo 7.0.0"></head><body itemscope="" itemtype="http://schema.org/WebPage"><div id="loading"><div class="cat"><div class="body"></div><div class="head"><div class="face"></div></div><div class="foot"><div class="tummy-end"></div><div class="bottom"></div><div class="legs left"></div><div class="legs right"></div></div><div class="paw"><div class="hands left"></div><div class="hands right"></div></div></div></div><div id="container"><header id="header" itemscope="" itemtype="http://schema.org/WPHeader"><div class="inner"><div id="brand"><div class="pjax"><h1 itemprop="name headline">LeetCode - 栈与队列专题</h1><div class="meta"><span class="item" title="创建时间：2022-05-19 22:57:23"><span class="icon"><i class="ic i-calendar"></i></span><span class="text">发表于</span><time itemprop="dateCreated datePublished" datetime="2022-05-19T22:57:23+08:00">2022-05-19</time></span><span class="item" title="本文字数"><span class="icon"><i class="ic i-pen"></i></span><span class="text">本文字数</span><span>30k</span><span class="text">字</span></span><span class="item" title="阅读时长"><span class="icon"><i class="ic i-clock"></i></span><span class="text">阅读时长</span><span>28 分钟</span></span></div></div></div><nav id="nav"><div class="inner"><div class="toggle"><div class="lines" aria-label="切换导航栏"><span class="line"></span><span class="line"></span><span class="line"></span></div></div><ul class="menu"><li class="item title"><a href="/" rel="start">Jiankychen</a></li></ul><ul class="right" id="rightNav"><li class="item theme"><i class="ic i-sun"></i></li><li class="item search"><i class="ic i-search"></i></li></ul></div></nav></div><div class="pjax" id="imgs"><ul><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/Y0hOs.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/8fe50780c15461b629c9aeab5a7f2acd.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/Y0iNK.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/99fb5ff897a82984470abf5e2a235d94.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/9b626c5ba21d7cb4dbcba2b507688bbb.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/2aabaeb8aca379b991071d1c41632741.jpg");"></li></ul></div></header><div id="waves"><svg class="waves" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 24 150 28" preserveAspectRatio="none" shape-rendering="auto"><defs><path id="gentle-wave" d="M-160 44c30 0 58-18 88-18s 58 18 88 18 58-18 88-18 58 18 88 18 v44h-352z"></path></defs><g class="parallax"><use xlink:href="#gentle-wave" x="48" y="0"></use><use xlink:href="#gentle-wave" x="48" y="3"></use><use xlink:href="#gentle-wave" x="48" y="5"></use><use xlink:href="#gentle-wave" x="48" y="7"></use></g></svg></div><main><div class="inner"><div class="pjax" id="main"><div class="article wrap"><div class="breadcrumb" itemlistelement="" itemscope="" itemtype="https://schema.org/BreadcrumbList"><i class="ic i-home"></i><span><a href="/">首页</a></span><i class="ic i-angle-right"></i><span class="current" itemprop="itemListElement" itemscope="itemscope" itemtype="https://schema.org/ListItem"><a href="/categories/Coding/" itemprop="item" rel="index" title="分类于Coding"><span itemprop="name">Coding<meta itemprop="position" content="0"></span></a></span></div><article class="post block" itemscope="itemscope" itemtype="http://schema.org/Article" lang="zh-CN"><link itemprop="mainEntityOfPage" href="https://jiankychen.github.io/leetcode-stacks&queues.html"><span hidden="hidden" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><meta itemprop="image" content="/assets/avatar.jpg"><meta itemprop="name" content="Jiankychen"><meta itemprop="description" content="Never put off till tomorrow what you can do today, "></span><span hidden="hidden" itemprop="publisher" itemscope="itemscope" itemtype="http://schema.org/Organization"><meta itemprop="name" content="Jiankychen's Blog"></span><div class="body md" itemprop="articleBody"><h1 id="leetcode-1047-删除字符串中的所有相邻重复项"><a class="anchor" href="#leetcode-1047-删除字符串中的所有相邻重复项">#</a> LeetCode 1047. 删除字符串中的所有相邻重复项</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/">1047. Remove All Adjacent Duplicates In String</a></p>
<p>给出由小写字母组成的字符串 <code>S</code> ，<strong>重复项删除操作</strong> 会选择两个相邻且相同的字母，并删除它们。</p>
<p>在 <code>S</code> 上反复执行重复项删除操作，直到无法继续删除。</p>
<p>在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：s = "abbaca"
输出："ca"
解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：s = "azxxzy"
输出："ay"
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>s.length</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">\le 10^5</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">5</span></span></span></span></span></span></span></span></span></span></span></li>
<li><code>s</code> 仅由小写英文字母组成</li>
</ul>
<h2 id="思路"><a class="anchor" href="#思路">#</a> 思路</h2>
<p>匹配问题 都是 栈 的强项</p>
<p>基本思路：遍历字符串，若当前字符与栈顶元素相等，将栈顶元素移除，否则，将字符压入栈中。遍历完字符串以后，栈内不再含有连续的重复字符，将栈内元素依次弹出、并填充到目标字符串即可</p>
<h2 id="method-1-栈"><a class="anchor" href="#method-1-栈">#</a> Method 1: 栈</h2>
<p>由于栈顶元素对应的是字符串的尾端，填充目标字符串时需按从右往左顺序填充</p>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>string <span class="token function">removeDuplicates</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token comment">// 将字符依次压入栈，若遇连续相同字符，则将栈顶元素移除</span></pre></td></tr><tr><td data-num="3"></td><td><pre> stack<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> stk<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">auto</span> c <span class="token operator">:</span> s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>stk<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&&</span> c <span class="token operator">==</span> stk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> stk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">else</span> stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>c<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token comment">// 将栈内字符添加到新字符串中（最先出栈的放到字符串末尾）</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">int</span> size <span class="token operator">=</span> stk<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> string <span class="token function">res</span><span class="token punctuation">(</span>size<span class="token punctuation">,</span> <span class="token char">' '</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> size <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="12"></td><td><pre> res<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> stk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token keyword">return</span> res<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 为字符串长度</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，栈所需空间（这里没有把目标字符串所需空间考虑在内）</p>
<blockquote>
<p>也可以将栈内元素按从左往右顺序填充到目标字符串，然后再对目标字符串进行翻转</p>
</blockquote>
<h2 id="method-2-字符串"><a class="anchor" href="#method-2-字符串">#</a> Method 2: 字符串</h2>
<p>在 C++ 中，由于标准库类型 <code>string</code> 本身就提供了类似 入栈 和 出栈 的接口，可直接将目标字符串作为栈</p>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>string <span class="token function">removeDuplicates</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> string res <span class="token operator">=</span> <span class="token string">""</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">auto</span> c <span class="token operator">:</span> s<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 从目标字符串尾部移除与 c 相同的字符</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>res<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&&</span> c <span class="token operator">==</span> res<span class="token punctuation">.</span><span class="token function">back</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="5"></td><td><pre> res<span class="token punctuation">.</span><span class="token function">pop_back</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">else</span> <span class="token comment">// 将字符 c 添加到目标字符串尾部</span></pre></td></tr><tr><td data-num="7"></td><td><pre> res<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>c<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">return</span> res<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 为字符串长度</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span>，没有把目标字符串所需空间考虑在内</p>
<p>参考：</p>
<ul>
<li><a target="_blank" rel="noopener" href="https://www.programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html">代码随想录</a></li>
<li><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/solution/shan-chu-zi-fu-chuan-zhong-de-suo-you-xi-4ohr/">力扣官方题解</a></li>
</ul>
<h1 id="leetcode-150-逆波兰表达式求值"><a class="anchor" href="#leetcode-150-逆波兰表达式求值">#</a> LeetCode 150. 逆波兰表达式求值</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/evaluate-reverse-polish-notation/">LeetCode 150. Evaluate Reverse Polish Notation</a></p>
<p>给你一个字符串数组 <code>tokens</code> ，表示一个根据 <strong>逆波兰表示法</strong> 表示的算术表达式。</p>
<p>请你计算该表达式。返回一个表示表达式值的整数。</p>
<p>注意：</p>
<ul>
<li>有效的算符为 <code>'+'</code> 、 <code>'-'</code> 、 <code>'*'</code> 和 <code>'/'</code> 。</li>
<li>每个操作数（运算对象）都可以是一个整数或者另一个表达式。</li>
<li>两个整数之间的除法总是 向零截断 。</li>
<li>表达式中不含除零运算。</li>
<li>输入是一个根据逆波兰表示法表示的算术表达式。</li>
<li>答案及所有中间计算结果可以用 <strong>32 位</strong> 整数表示。</li>
</ul>
<p></p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：tokens = ["2","1","+","3","*"]
输出：9
解释：((2 + 1) * 3) = 9
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：tokens = ["4","13","5","/","+"]
输出：6
解释：(4 + (13 / 5)) = 6
</code></pre>
<p><strong>示例 3：</strong></p>
<pre><code>输入：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
</code></pre>
<p></p>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>tokens.length</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup></mrow><annotation encoding="application/x-tex">\le 10^4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span></span></span></span></span></span></span></span></li>
<li><code>tokens[i]</code> 是一个算符 （ <code>"+"</code> 、 <code>"-"</code> 、 <code>"*"</code> 或 <code>"/"</code> ），或是在范围 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">[</mo><mo>−</mo><mn>200</mn><mo separator="true">,</mo><mn>200</mn><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">[-200, 200]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">−</span><span class="mord">200</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">200</span><span class="mclose">]</span></span></span></span> 内的一个整数</li>
</ul>
<h2 id="思路-2"><a class="anchor" href="#思路-2">#</a> 思路</h2>
<p>逆波兰表达式，即，<strong>后缀表达式</strong>（运算符写在两个操作数的后面）</p>
<p>日常使用的是中缀表达式（运算符写在两个操作数的中间）</p>
<p>例如， <code>2 + 3</code> 就是中缀表达式，对应的后缀表达式是 <code>2 3 +</code></p>
<p>由此，本题的求解思路为：</p>
<ol>
<li>
<p>定义一个 栈</p>
</li>
<li>
<p>遍历数组 <code>tokens</code> ，若遇到的是数字，则将数字压入栈，若遇到的是 <code>"+"</code> 、 <code>"-"</code> 、 <code>"*"</code> 、 <code>"/"</code> 运算符，则从栈内取出两个数字进行计算，然后将计算结果压入栈中</p>
</li>
<li>
<p>遍历结束时，栈内剩余元素即为整个后缀表达式的计算结果</p>
</li>
</ol>
<p>注意，数组 <code>tokens</code> 内的元素是 <code>string</code> 类型的对象，<strong>将 <code>string</code> 型的数字压入栈前需将其转换成 <code>int</code> 型</strong></p>
<ul>
<li>调用 <code>stoi</code> 函数即可，参考 <a target="_blank" rel="noopener" href="http://www.cplusplus.com/reference/string/stoi/?kw=stoi">cplusplus：std::stoi</a></li>
</ul>
<h2 id="method-栈"><a class="anchor" href="#method-栈">#</a> Method: 栈</h2>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 计算后缀表达式，并将结果压入栈</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">void</span> <span class="token function">compute</span><span class="token punctuation">(</span>stack<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">&</span>stk<span class="token punctuation">,</span> string c<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">int</span> right <span class="token operator">=</span> stk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 右操作数</span></pre></td></tr><tr><td data-num="4"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">int</span> left <span class="token operator">=</span> stk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 左操作数</span></pre></td></tr><tr><td data-num="6"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>c <span class="token operator">==</span> <span class="token string">"+"</span><span class="token punctuation">)</span> stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>left <span class="token operator">+</span> right<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>c <span class="token operator">==</span> <span class="token string">"-"</span><span class="token punctuation">)</span> stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>left <span class="token operator">-</span> right<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>c <span class="token operator">==</span> <span class="token string">"*"</span><span class="token punctuation">)</span> stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>left <span class="token operator">*</span> right<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>c <span class="token operator">==</span> <span class="token string">"/"</span><span class="token punctuation">)</span> stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>left <span class="token operator">/</span> right<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="12"></td><td><pre></pre></td></tr><tr><td data-num="13"></td><td><pre><span class="token keyword">int</span> <span class="token function">evalRPN</span><span class="token punctuation">(</span>vector<span class="token operator"><</span>string<span class="token operator">></span><span class="token operator">&</span> tokens<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="14"></td><td><pre> stack<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> stk<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">auto</span> c <span class="token operator">:</span> tokens<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>c <span class="token operator">==</span> <span class="token string">"+"</span> <span class="token operator">||</span> c <span class="token operator">==</span> <span class="token string">"-"</span> <span class="token operator">||</span> c <span class="token operator">==</span> <span class="token string">"*"</span> <span class="token operator">||</span> c <span class="token operator">==</span> <span class="token string">"/"</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token function">compute</span><span class="token punctuation">(</span>stk<span class="token punctuation">,</span> c<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token keyword">else</span></pre></td></tr><tr><td data-num="19"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token function">stoi</span><span class="token punctuation">(</span>c<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 将 string 类型转成 int 型</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token keyword">int</span> ans <span class="token operator">=</span> stk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="22"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="23"></td><td><pre> <span class="token keyword">return</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="24"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 为 <code>tokens</code> 的长度</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，栈所需空间</p>
<h1 id="leetcode-155-最小栈"><a class="anchor" href="#leetcode-155-最小栈">#</a> LeetCode 155. 最小栈</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/min-stack/">155. Min Stack</a></p>
<p>设计一个支持 <code>push</code> ， <code>pop</code> ， <code>top</code> 操作，并能在常数时间内检索到最小元素的栈。</p>
<p>实现 <code>MinStack</code> 类:</p>
<ul>
<li><code>MinStack()</code> 初始化堆栈对象。</li>
<li><code>void push(int val)</code> 将元素 val 推入堆栈。</li>
<li><code>void pop()</code> 删除堆栈顶部的元素。</li>
<li><code>int top()</code> 获取堆栈顶部的元素。</li>
<li><code>int getMin()</code> 获取堆栈中的最小元素。</li>
</ul>
<p><strong>示例 1：</strong></p>
<pre><code>输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>−</mo><msup><mn>2</mn><mn>31</mn></msup><mo>≤</mo></mrow><annotation encoding="application/x-tex">-2^{31} \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.9501em;vertical-align:-0.136em;"></span><span class="mord">−</span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">31</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>val</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><msup><mn>2</mn><mn>31</mn></msup><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">\le 2^{31} - 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8974em;vertical-align:-0.0833em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">31</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span></li>
<li><code>pop</code> 、 <code>top</code> 和 <code>getMin</code> 操作总是在 非空栈 上调用</li>
<li><code>push</code> 、 <code>pop</code> 、 <code>top</code> 和 <code>getMin</code> 最多被调用 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>3</mn><mo>×</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup></mrow><annotation encoding="application/x-tex">3 \times 10^4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7278em;vertical-align:-0.0833em;"></span><span class="mord">3</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span></span></span></span></span></span></span></span> 次</li>
</ul>
<h2 id="method-辅助栈"><a class="anchor" href="#method-辅助栈">#</a> Method: 辅助栈</h2>
<p>算法思路：</p>
<p>定义一个元素栈（记作 stk），用于存储每个元素</p>
<p>定义一个辅助栈（记作 minStk），用于存储与每个元素对应的最小值（与元素值同步插入与删除）</p>
<ul>
<li>
<p>当一个元素要入栈到 stk 时，我们取辅助栈 minStk 的栈顶元素与当前元素比较，将最小值插入辅助栈 minStk 中</p>
</li>
<li>
<p>当一个元素要从 stk 中弹出时，我们把辅助栈 minStk 的栈顶元素也相应弹出</p>
</li>
<li>
<p>在任意时刻，栈 stk 内的元素最小值就是辅助栈 minStk 的栈顶元素</p>
</li>
</ul>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">class</span> <span class="token class-name">MinStack</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">public</span><span class="token operator">:</span></pre></td></tr><tr><td data-num="3"></td><td><pre> stack<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> stk<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> stack<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> minStk<span class="token punctuation">;</span> <span class="token comment">// 辅助栈</span></pre></td></tr><tr><td data-num="5"></td><td><pre></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token function">MinStack</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="7"></td><td><pre> minStk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>INT_MAX<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 初始化辅助栈</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="9"></td><td><pre> </pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">void</span> <span class="token function">push</span><span class="token punctuation">(</span><span class="token keyword">int</span> val<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="11"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>val<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> minStk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token function">min</span><span class="token punctuation">(</span>val<span class="token punctuation">,</span> minStk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre> </pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token keyword">void</span> <span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="16"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre> minStk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="19"></td><td><pre> </pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token keyword">int</span> <span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token keyword">return</span> stk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="23"></td><td><pre> </pre></td></tr><tr><td data-num="24"></td><td><pre> <span class="token keyword">int</span> <span class="token function">getMin</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token keyword">return</span> minStk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="26"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="27"></td><td><pre><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="28"></td><td><pre></pre></td></tr><tr><td data-num="29"></td><td><pre><span class="token comment">/**</span></pre></td></tr><tr><td data-num="30"></td><td><pre> * Your MinStack object will be instantiated and called as such:</pre></td></tr><tr><td data-num="31"></td><td><pre> * MinStack* obj = new MinStack();</pre></td></tr><tr><td data-num="32"></td><td><pre> * obj->push(val);</pre></td></tr><tr><td data-num="33"></td><td><pre> * obj->pop();</pre></td></tr><tr><td data-num="34"></td><td><pre> * int param_3 = obj->top();</pre></td></tr><tr><td data-num="35"></td><td><pre> * int param_4 = obj->getMin();</pre></td></tr><tr><td data-num="36"></td><td><pre> */</pre></td></tr></tbody></table></figure><p>时间复杂度：入栈、出栈、获取栈顶元素、获取最小元素的时间复杂度均为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span></p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，其中 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 为元素个数，考虑了辅助栈所需的额外空间</p>
<p>参考：<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/min-stack/solution/zui-xiao-zhan-by-leetcode-solution/">leetcode-solution</a></p>
<h1 id="leetcode-20-有效的括号"><a class="anchor" href="#leetcode-20-有效的括号">#</a> LeetCode 20. 有效的括号</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/valid-parentheses/">LeetCode 20. Valid Parentheses</a></p>
<p>给定一个只包括 <code>'('</code> ， <code>')'</code> ， <code>'{'</code> ， <code>'}'</code> ， <code>'['</code> ， <code>']'</code> 的字符串 <code>s</code> ，判断字符串是否有效。</p>
<p>有效字符串需满足：</p>
<ul>
<li>左括号必须用相同类型的右括号闭合。</li>
<li>左括号必须以正确的顺序闭合。</li>
<li>每个右括号都有一个对应的相同类型的左括号。</li>
</ul>
<p><strong>示例 1：</strong></p>
<pre><code>输入：s = "()"
输出：true
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：s = "()[]{}"
输出：true
</code></pre>
<p><strong>示例 3：</strong></p>
<pre><code>输入：s = "(]"
输出：false
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>s.length</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup></mrow><annotation encoding="application/x-tex">\le 10^4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span></span></span></span></span></span></span></span></li>
<li><code>s</code> 仅包含括号 <code>'()[]{}'</code></li>
</ul>
<h2 id="思路-3"><a class="anchor" href="#思路-3">#</a> 思路</h2>
<p>从左往右遍历字符串时，后遇到的左括号需要先匹配，与栈后进先出的特点不谋而合</p>
<p>因此，<strong>括号匹配问题可以使用 栈 来解决</strong></p>
<p>基本思路：遍历字符串，若遇到左括号，则将其入栈，若遇到右括号，则将对应栈顶左括号出栈</p>
<p>考察 括号不匹配 的三种情况：</p>
<ul>
<li>存在多余的左括号：在这种情况下，待字符串遍历结束后，栈不为空</li>
<li>存在多余的右括号：字符串未遍历完，栈已经为空</li>
<li>括号没有多余，但是括号的方向不对应：在遍历字符串过程中，遍历到的右括号无法与栈顶左括号匹配</li>
</ul>
<p>若字符串遍历结束后，栈为空，则说明括号全部匹配</p>
<h2 id="method-1-栈-map"><a class="anchor" href="#method-1-栈-map">#</a> Method 1: 栈 + map</h2>
<p>栈 存储的是 待匹配的左括号</p>
<p>哈希 map 用来存储可以匹配的括号类型，即：哈希表的 key 为右括号，value 为相同类型的左括号，这样查询 2 个括号是否对应只需 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span> 时间复杂度</p>
<p>具体可参考 <a target="_blank" rel="noopener" href="https://leetcode.cn/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/">力扣官方题解：有效的括号</a> 和 <a target="_blank" rel="noopener" href="https://leetcode.cn/problems/valid-parentheses/solution/valid-parentheses-fu-zhu-zhan-fa-by-jin407891080/">Krahets：有效的括号</a></p>
<h2 id="method-2-栈"><a class="anchor" href="#method-2-栈">#</a> Method 2: 栈</h2>
<p>遍历字符串过程中，若遇到左括号，可将对应的右括号压入栈，后续遇到右括号时，只需将其与栈顶元素进行比较即可，若相等，则匹配，否则不匹配</p>
<p>即，栈 存储的是 与左括号对应的右括号</p>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">bool</span> <span class="token function">isValid</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token number">2</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span> <span class="token comment">// 括号数为奇数，直接返回 false</span></pre></td></tr><tr><td data-num="3"></td><td><pre> stack<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> stk<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">auto</span> c <span class="token operator">:</span> s<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 范围 for</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token comment">// 当 c 为 左括号 时，把对应的 右括号 压入栈</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>c <span class="token operator">==</span> <span class="token char">'('</span><span class="token punctuation">)</span> stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token char">')'</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>c <span class="token operator">==</span> <span class="token char">'['</span><span class="token punctuation">)</span> stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token char">']'</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>c <span class="token operator">==</span> <span class="token char">'{'</span><span class="token punctuation">)</span> stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token char">'}'</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token comment">// 当栈为空，或者，c 是 右括号 但 不等于栈顶元素，匹配失败</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>stk<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">||</span> c <span class="token operator">!=</span> stk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token comment">//c 是 右括号 且 等于栈顶元素，匹配成功，从栈顶移除左括号</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token keyword">else</span> stk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token comment">// 所有括号均已遍历完成，若栈为空，则匹配成功</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token keyword">return</span> stk<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，遍历字符串</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，栈所需空间</p>
<p>参考：<a target="_blank" rel="noopener" href="https://www.programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html#%E9%A2%98%E5%A4%96%E8%AF%9D">代码随想录：有效的括号</a></p>
<h1 id="leetcode-225-用队列实现栈"><a class="anchor" href="#leetcode-225-用队列实现栈">#</a> LeetCode 225. 用队列实现栈</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/implement-stack-using-queues/">LeetCode 225. Implement Stack using Queues</a></p>
<p>请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（ <code>push</code> 、 <code>top</code> 、 <code>pop</code> 和 <code>empty</code> ）。</p>
<p>实现 MyStack 类：</p>
<ul>
<li><code>void push(int x)</code> 将元素 <code>x</code> 压入栈顶。</li>
<li><code>int pop()</code> 移除并返回栈顶元素。</li>
<li><code>int top()</code> 返回栈顶元素。</li>
<li><code>boolean empty()</code> 如果栈是空的，返回 <code>true</code> ；否则，返回 <code>false</code> 。</li>
</ul>
<p><strong>注意：</strong></p>
<ul>
<li>你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。</li>
<li>你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列，只要是标准的队列操作即可。</li>
</ul>
<p></p>
<p><strong>示例 1：</strong></p>
<pre><code>输入
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
</code></pre>
<p></p>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>x</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>9</mn></mrow><annotation encoding="application/x-tex">\le 9</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">9</span></span></span></span></li>
<li>最多调用 100 次 <code>push</code> 、 <code>pop</code> 、 <code>top</code> 和 <code>empty</code></li>
<li>每次调用 <code>pop</code> 和 <code>top</code> 都保证栈不为空</li>
</ul>
<p><strong>进阶：</strong> 你能否仅用一个队列来实现栈。</p>
<h2 id="思路-4"><a class="anchor" href="#思路-4">#</a> 思路</h2>
<p>栈 的特点是 后进先出 ，队列 的特点是 先进先出</p>
<p>可定义一个队列，使得 最先入栈的元素 放在 队首 ，最后入栈的元素 放在 队尾</p>
<ul>
<li>
<p>对于入栈操作，只需将元素添加到队尾</p>
</li>
<li>
<p>对于出栈操作，需将队尾元素移除并返回</p>
</li>
<li>
<p>为获取栈顶元素，可先将栈顶元素出栈，并记录其值（本题定义的 出栈 函数具有返回值），然后再将其压入栈</p>
</li>
<li>
<p>判断栈是否为空，只需判断用来存储栈元素的队列是否为空</p>
</li>
</ul>
<p>特别地，出栈操作可通过两个队列协同实现，也可仅用一个队列实现</p>
<h2 id="method-两个队列"><a class="anchor" href="#method-两个队列">#</a> Method: 两个队列</h2>
<p>定义队列 <code>que1</code> ，用于存储 栈 的数据（ 最先入栈的元素 放在 队首 、最后入栈的元素 放在 队尾 ）</p>
<p>定义队列 <code>que2</code> ，在 出栈 操作中，用于临时存放队列 <code>que1</code> 的前 <code>que1.size() - 1</code> 个元素，以便将 <code>que1</code> 队尾元素移除</p>
<p>时间复杂度：入栈操作 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span>，出栈操作 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，读取栈顶元素 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，判断栈是否为空 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 是元素个数</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<h2 id="method-一个队列"><a class="anchor" href="#method-一个队列">#</a> Method: 一个队列</h2>
<p>由于队列具有先进先出的特性，无需额外定义一个队列 <code>que2</code> 来实现 出栈 过程中元素的临时存放，即，直接将元素重新入队 <code>que1</code> 即可，这样就能使得最初的队尾元素出现在队首</p>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">class</span> <span class="token class-name">MyStack</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">public</span><span class="token operator">:</span></pre></td></tr><tr><td data-num="3"></td><td><pre> queue<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> que<span class="token punctuation">;</span> <span class="token comment">// 最先入栈的放在 que 队首，最后入栈的放在 que 队尾</span></pre></td></tr><tr><td data-num="4"></td><td><pre></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token function">MyStack</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="6"></td><td><pre></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="8"></td><td><pre> </pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">void</span> <span class="token function">push</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="10"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="12"></td><td><pre> </pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">int</span> <span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token keyword">int</span> length <span class="token operator">=</span> que<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 记录 que1 的长度，注意，不能直接将 que.size () 作为 for 循环的判定条件</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token comment">// 将 que 前 length - 1 个元素依次移出，然后放入队尾，使得最初的队尾元素出现在队首</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token keyword">int</span> temp <span class="token operator">=</span> que<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="19"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>temp<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token comment">// 记录最初的队尾元素值，并将其移除</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token keyword">int</span> ans <span class="token operator">=</span> que<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="23"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="24"></td><td><pre> <span class="token keyword">return</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="26"></td><td><pre> </pre></td></tr><tr><td data-num="27"></td><td><pre> <span class="token keyword">int</span> <span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="28"></td><td><pre> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 复用已经定义的 MyStack 类别的 pop () 函数，将栈顶元素弹出</span></pre></td></tr><tr><td data-num="29"></td><td><pre> <span class="token function">push</span><span class="token punctuation">(</span>ans<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 再将其压入栈</span></pre></td></tr><tr><td data-num="30"></td><td><pre> <span class="token keyword">return</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="31"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="32"></td><td><pre> </pre></td></tr><tr><td data-num="33"></td><td><pre> <span class="token keyword">bool</span> <span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="34"></td><td><pre> <span class="token keyword">return</span> que<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token boolean">true</span> <span class="token operator">:</span> <span class="token boolean">false</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="35"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="36"></td><td><pre><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="37"></td><td><pre></pre></td></tr><tr><td data-num="38"></td><td><pre><span class="token comment">/**</span></pre></td></tr><tr><td data-num="39"></td><td><pre> * Your MyStack object will be instantiated and called as such:</pre></td></tr><tr><td data-num="40"></td><td><pre> * MyStack* obj = new MyStack();</pre></td></tr><tr><td data-num="41"></td><td><pre> * obj->push(x);</pre></td></tr><tr><td data-num="42"></td><td><pre> * int param_2 = obj->pop();</pre></td></tr><tr><td data-num="43"></td><td><pre> * int param_3 = obj->top();</pre></td></tr><tr><td data-num="44"></td><td><pre> * bool param_4 = obj->empty();</pre></td></tr><tr><td data-num="45"></td><td><pre> */</pre></td></tr></tbody></table></figure><p>时间复杂度：入栈操作 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span>，出栈操作 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，读取栈顶元素 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，判断栈是否为空 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 是元素个数</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<blockquote>
<p>事实上，也可以将 最后入栈的元素 放在 队首 、最先入栈的元素 放在 队尾 ，即，队列 的 前端 和 后端 分别对应 栈顶 和 栈底 。<br>
但是，这种情况下的 入栈 操作则会复杂很多，对应的时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，而 出栈 和 读取栈顶元素 则会简单很多，对应的时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span><br>
可参考 <a target="_blank" rel="noopener" href="https://leetcode.cn/problems/implement-stack-using-queues/solution/yong-dui-lie-shi-xian-zhan-by-leetcode-solution/">力扣官方题解：用队列实现栈</a></p>
</blockquote>
<h1 id="leetcode-227-基本计算器-ii"><a class="anchor" href="#leetcode-227-基本计算器-ii">#</a> LeetCode 227. 基本计算器 II</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/basic-calculator-ii/description/">227. 基本计算器 II</a></p>
<p>给你一个字符串表达式 <code>s</code> ，请你实现一个基本计算器来计算并返回它的值</p>
<p>整数除法仅保留整数部分</p>
<p>你可以假设给定的表达式总是有效的。所有中间结果将在 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">[</mo><mo>−</mo><msup><mn>2</mn><mn>31</mn></msup><mo separator="true">,</mo><msup><mn>2</mn><mn>31</mn></msup><mo>−</mo><mn>1</mn><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">[-2^{31}, 2^{31} - 1]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.0641em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">−</span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">31</span></span></span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">31</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">]</span></span></span></span> 的范围内</p>
<p>注意：不允许使用任何将字符串作为数学表达式计算的内置函数（例如 <code>eval()</code> ）</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：s = "3+2*2"
输出：7
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：s = " 3/2 "
输出：1
</code></pre>
<p><strong>示例 3：</strong></p>
<pre><code>输入：s = " 3+5 / 2 "
输出：5
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li>1 <= s.length <= 3 * 10<sup>5</sup></li>
<li>s 由整数和算符 ( <code>'+'</code> , <code>'-'</code> , <code>'*'</code> , <code>'/'</code> ) 组成，中间由一些 <strong>空格</strong> 隔开</li>
<li>s 表示一个 <strong>有效表达式</strong></li>
<li>表达式中的所有整数都是非负整数，且在范围 [0, 2<sup>31</sup> - 1] 内</li>
<li>题目数据保证答案是一个 <strong>32-bit 整数</strong></li>
</ul>
<h2 id="method-栈-2"><a class="anchor" href="#method-栈-2">#</a> Method: 栈</h2>
<h2 id="算法思路"><a class="anchor" href="#算法思路">#</a> 算法思路</h2>
<p>由于乘除优先于加减计算，可以先进行所有乘除运算，并将这些乘除运算的结果放回原表达式的相应位置，最终，整个表达式的结果就等于一系列整数加减后的值</p>
<p>因此，可以用一个栈保存这些（进行乘除运算后的）整数的值</p>
<ul>
<li>对于 <code>'+'</code> 后面的数字，将其直接压入栈中</li>
<li>对于 <code>'-'</code> 后面的数组，将其相反数压入栈中</li>
<li>对于 <code>'*'</code> 或 <code>'/'</code> 后面的数字，可直接将其与栈顶元素计算，并使用计算结果替换栈顶元素</li>
</ul>
<p>最后将栈中元素进行累加，即可得到字符串表达式的值</p>
<h2 id="算法流程"><a class="anchor" href="#算法流程">#</a> 算法流程</h2>
<p>定义 <code>num</code> 为当前处理的整数</p>
<p>定义变量 <code>sign</code> 为整数之前的运算符（将第一个数字之前的运算符视为加号）</p>
<p>遍历字符串 <code>s</code></p>
<ul>
<li>若当前字符 <code>s[i]</code> 为数字字符，则更新当前整数值 <code>num</code> ： <code>num = num * 10 + (s[i] - '0')</code></li>
<li>若当前字符 <code>s[i]</code> 为运算符或者字符串最后一个字符，则说明已经遍历到了整数 <code>num</code> 的末尾，此时需根据整数 <code>num</code> 之前的运算符 <code>sign</code> 对 <code>num</code> 进行处理：
<ul>
<li>若 <code>sign</code> 为 <code>'+'</code> ：将 <code>num</code> 压入栈；</li>
<li>若 <code>sign</code> 为 <code>'-'</code> ：将 <code>- num</code> 压入栈；</li>
<li>若 <code>sign</code> 为 <code>'*'</code> 或 <code>'/'</code> ：将其与栈顶元素计算，并将栈顶元素替换为计算结果</li>
</ul>
</li>
<li>待处理 <code>num</code> 后，更新 <code>sign</code> 为当前遍历到的运算符</li>
</ul>
<p>最后，将栈中元素进行累加</p>
<blockquote>
<p>这里可以用 <code>vector</code> 数组模拟栈，以便最后计算栈中元素之和</p>
</blockquote>
<h2 id="代码实现"><a class="anchor" href="#代码实现">#</a> 代码实现</h2>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">int</span> <span class="token function">calculate</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> stk<span class="token punctuation">;</span> <span class="token comment">// 模拟栈</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">int</span> num <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// 当前处理的整数</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">char</span> sign <span class="token operator">=</span> <span class="token char">'+'</span><span class="token punctuation">;</span> <span class="token comment">// 整数前面的运算符</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token operator">++</span>i<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token comment">// 遇到数字字符，计算对应的整数</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">isdigit</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="8"></td><td><pre> num <span class="token operator">=</span> num <span class="token operator">*</span> <span class="token number">10</span> <span class="token operator">+</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">-</span> <span class="token char">'0'</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token comment">// 遇到算术符或者字符串末尾，执行算术运算</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token operator">!</span><span class="token function">isdigit</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">&&</span> <span class="token operator">!</span><span class="token function">isspace</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">||</span> i <span class="token operator">==</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>sign <span class="token operator">==</span> <span class="token char">'+'</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="13"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>num<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>sign <span class="token operator">==</span> <span class="token char">'-'</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="15"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token operator">-</span>num<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>sign <span class="token operator">==</span> <span class="token char">'*'</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="17"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">back</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">*=</span> num<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>sign <span class="token operator">==</span> <span class="token char">'/'</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="19"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">back</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">/=</span> num<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="21"></td><td><pre> sign <span class="token operator">=</span> s<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// 更新 sign 为当前遍历到的运算符</span></pre></td></tr><tr><td data-num="22"></td><td><pre> num <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// 重置整数</span></pre></td></tr><tr><td data-num="23"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="24"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="25"></td><td><pre></pre></td></tr><tr><td data-num="26"></td><td><pre> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="27"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> tmp <span class="token operator">:</span> stk<span class="token punctuation">)</span> ans <span class="token operator">+=</span> tmp<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="28"></td><td><pre> <span class="token keyword">return</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="29"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><h2 id="复杂度分析"><a class="anchor" href="#复杂度分析">#</a> 复杂度分析</h2>
<p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 为字符串长度</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<h2 id="参考资料"><a class="anchor" href="#参考资料">#</a> 参考资料</h2>
<p>参考：</p>
<ul>
<li><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/basic-calculator-ii/solutions/648647/ji-ben-ji-suan-qi-ii-by-leetcode-solutio-cm28/">力扣官方题解</a></li>
<li><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/basic-calculator-ii/solutions/648832/shi-yong-shuang-zhan-jie-jue-jiu-ji-biao-c65k/">宫水三叶：双栈解法</a></li>
</ul>
<h1 id="leetcode-232-用栈实现队列"><a class="anchor" href="#leetcode-232-用栈实现队列">#</a> LeetCode 232. 用栈实现队列</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/implement-queue-using-stacks/">LeetCode 232. Implement Queue using Stacks</a></p>
<p>请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（ <code>push</code> 、 <code>pop</code> 、 <code>peek</code> 、 <code>empty</code> ）：</p>
<p>实现 <code>MyQueue</code> 类：</p>
<ul>
<li><code>void push(int x)</code> 将元素 <code>x</code> 推到队列的末尾</li>
<li><code>int pop()</code> 从队列的开头移除并返回元素</li>
<li><code>int peek()</code> 返回队列开头的元素</li>
<li><code>boolean empty()</code> 如果队列为空，返回 <code>true</code> ；否则，返回 <code>false</code></li>
</ul>
<p><strong>说明：</strong></p>
<ul>
<li>你 <strong>只能</strong> 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。</li>
<li>你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。</li>
</ul>
<p><strong>示例 1：</strong></p>
<pre><code>输入
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
</code></pre>
<p></p>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>x</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>9</mn></mrow><annotation encoding="application/x-tex">\le 9</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">9</span></span></span></span></li>
<li>最多调用 100 次 <code>push</code> 、 <code>pop</code> 、 <code>peek</code> 和 <code>empty</code></li>
<li>假设所有操作都是有效的 （例如，一个空的队列不会调用 <code>pop</code> 或者 <code>peek</code> 操作）</li>
</ul>
<p><strong>进阶：</strong> 你能否实现每个操作均摊时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span> 的队列？换句话说，执行 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 个操作的总时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span> ，即使其中一个操作可能花费较长时间。</p>
<h2 id="思路-5"><a class="anchor" href="#思路-5">#</a> 思路</h2>
<p>栈具有后进先出的特性</p>
<p>若将一个栈的所有元素移入到另一个栈中，元素的排列顺序会变得与之前相反</p>
<h2 id="method"><a class="anchor" href="#method">#</a> Method</h2>
<p>解题思路：</p>
<ol>
<li>
<p>定义两个栈， <code>stk1</code> 和 <code>stk2</code></p>
<ul>
<li>栈 <code>stk1</code> 用来作为存储队列，即，最先入队的在 <code>stk1</code> 栈顶，最后入队的在 <code>stk1</code> 栈底</li>
<li>栈 <code>stk2</code> 作为临时存储空间，用来协助实现队列的功能</li>
</ul>
</li>
<li>
<p><code>void push(int x)</code> 函数的实现：</p>
<ul>
<li>若 <code>stk1</code> 非空：先将 <code>stk1</code> 内的所有元素都移出来，放进 <code>stk2</code> ，然后将 <code>x</code> 压入栈 <code>stk1</code> ，将 <code>stk2</code> 内的元素移回 <code>stk1</code></li>
<li>若 <code>stk1</code> 为空，直接将 <code>x</code> 压入栈 <code>stk1</code> 即可</li>
</ul>
</li>
<li>
<p><code>int pop()</code> 函数的实现：</p>
<ul>
<li>记录 <code>stk1</code> 栈顶元素值，并弹出 <code>stk1</code> 栈顶元素，返回其值</li>
</ul>
</li>
<li>
<p><code>int peek()</code> 函数的实现：</p>
<ul>
<li>直接返回 <code>stk1</code> 栈顶元素值即可</li>
</ul>
</li>
<li>
<p><code>bool empty()</code> 函数的实现：</p>
<ul>
<li>判断 <code>stk1</code> 是否为空即可</li>
</ul>
</li>
</ol>
<blockquote>
<p>另，也可以 “将最先入队的放 <code>stk1</code> 栈底，最后入队的在 <code>stk1</code> 栈顶” ，此时：入队操作可直接将 <code>x</code> 压入栈 <code>stk1</code> ；出队操作需将 <code>stk1</code> 栈底以上的元素全都临时存放到 <code>stk2</code> ，待 <code>stk1</code> 栈底元素弹出后，再将 <code>stk2</code> 所有元素移回 <code>stk1</code></p>
</blockquote>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">class</span> <span class="token class-name">MyQueue</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">public</span><span class="token operator">:</span></pre></td></tr><tr><td data-num="3"></td><td><pre></pre></td></tr><tr><td data-num="4"></td><td><pre> stack<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> stk1<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> stack<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> stk2<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token function">MyQueue</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="8"></td><td><pre></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="10"></td><td><pre> </pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">void</span> <span class="token function">push</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>stk1<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">//stk1 非空</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>stk1<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 将 stk1 元素压入栈 stk2</span></pre></td></tr><tr><td data-num="14"></td><td><pre> stk2<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>stk1<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre> stk1<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="17"></td><td><pre> stk1<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 将 x 压入栈 stk1</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>stk2<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 将 stk2 元素放回栈 stk1</span></pre></td></tr><tr><td data-num="19"></td><td><pre> stk1<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>stk2<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> stk2<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="23"></td><td><pre> <span class="token keyword">else</span> <span class="token comment">//stk1 为空，直接将 x 压入栈 stk1</span></pre></td></tr><tr><td data-num="24"></td><td><pre> stk1<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="26"></td><td><pre> </pre></td></tr><tr><td data-num="27"></td><td><pre> <span class="token keyword">int</span> <span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="28"></td><td><pre> <span class="token keyword">int</span> ans <span class="token operator">=</span> stk1<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="29"></td><td><pre> stk1<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="30"></td><td><pre> <span class="token keyword">return</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="31"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="32"></td><td><pre> </pre></td></tr><tr><td data-num="33"></td><td><pre> <span class="token keyword">int</span> <span class="token function">peek</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="34"></td><td><pre> <span class="token keyword">int</span> ans <span class="token operator">=</span> stk1<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="35"></td><td><pre> <span class="token keyword">return</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="36"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="37"></td><td><pre> </pre></td></tr><tr><td data-num="38"></td><td><pre> <span class="token keyword">bool</span> <span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="39"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>stk1<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token boolean">true</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="40"></td><td><pre> <span class="token keyword">return</span> <span class="token boolean">false</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="41"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="42"></td><td><pre><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="43"></td><td><pre></pre></td></tr><tr><td data-num="44"></td><td><pre><span class="token comment">/**</span></pre></td></tr><tr><td data-num="45"></td><td><pre> * Your MyQueue object will be instantiated and called as such:</pre></td></tr><tr><td data-num="46"></td><td><pre> * MyQueue* obj = new MyQueue();</pre></td></tr><tr><td data-num="47"></td><td><pre> * obj->push(x);</pre></td></tr><tr><td data-num="48"></td><td><pre> * int param_2 = obj->pop();</pre></td></tr><tr><td data-num="49"></td><td><pre> * int param_3 = obj->peek();</pre></td></tr><tr><td data-num="50"></td><td><pre> * bool param_4 = obj->empty();</pre></td></tr><tr><td data-num="51"></td><td><pre> */</pre></td></tr></tbody></table></figure><p>注意，标准库实现的栈和队列，其成员函数 <code>pop()</code> 没有返回值，不能作为右值； <code>top()</code> 具有返回值，可以作为右值</p>
<p>另外，关于 <code>peek()</code> 函数的实现，可以直接调用已经定义了的 <code>MyQueue</code> 类别的 <code>pop()</code> 函数，即，通过函数的复用来实现。这样可以降低出错的可能性</p>
<h1 id="leetcode-239-滑动窗口最大值"><a class="anchor" href="#leetcode-239-滑动窗口最大值">#</a> LeetCode 239. 滑动窗口最大值</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/sliding-window-maximum/">239. Sliding Window Maximum</a></p>
<p>给你一个整数数组 <code>nums</code> ，有一个大小为 <code>k</code> 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 <code>k</code> 个数字。滑动窗口每次只向右移动一位。</p>
<p>返回 滑动窗口中的最大值 。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- ------
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：nums = [1], k = 1
输出：[1]
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>nums.length</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">\le 10^5</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">5</span></span></span></span></span></span></span></span></span></span></span></li>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>−</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup><mo>≤</mo></mrow><annotation encoding="application/x-tex">-10^4 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.9501em;vertical-align:-0.136em;"></span><span class="mord">−</span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>nums[i]</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>4</mn></msup></mrow><annotation encoding="application/x-tex">\le 10^4</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">4</span></span></span></span></span></span></span></span></span></span></span></li>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>k</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo></mrow><annotation encoding="application/x-tex">\le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span></span></span></span> <code>nums.length</code></li>
</ul>
<h2 id="思路-6"><a class="anchor" href="#思路-6">#</a> 思路：</h2>
<p>数组长为 <code>nums.size()</code> ，窗口长为 <code>k</code> ，一共有 <code>nums.size() - k + 1</code> 个窗口</p>
<p>若采用暴力法，对每个窗口求最大值需要 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(k)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mclose">)</span></span></span></span> 的时间复杂度，则总时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mi>k</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n k)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.03148em;">nk</span><span class="mclose">)</span></span></span></span></p>
<p>针对本题的数据，暴力法会超时</p>
<p>本题有三种求解思路：可参考 <a target="_blank" rel="noopener" href="https://leetcode.cn/problems/sliding-window-maximum/solution/dong-hua-yan-shi-dan-diao-dui-lie-239hua-hc5u/">力扣官方题解</a></p>
<ul>
<li>优先队列（堆）</li>
<li>单调队列</li>
<li>分块 + 预处理</li>
</ul>
<h2 id="method-1-优先队列"><a class="anchor" href="#method-1-优先队列">#</a> Method 1: 优先队列</h2>
<p>可以利用 最大化堆，即，根节点元素值最大的二叉堆， 来维护窗口的最大值</p>
<blockquote>
<p>有关 最大化堆 ，可参考 <a href="https://jiankychen.github.io/posts/a21107fc">优先级队列</a></p>
</blockquote>
<p>算法流程：</p>
<ol>
<li>
<p>定义一个 优先队列 ，其中，队列每个元素都是一个二元组，存储了 <code>nums</code> 数组元素值和元素下标，即： <code>priority_queue<pair<int, int>> que;</code></p>
</li>
<li>
<p>将 <code>nums</code> 数组的前 <code>k</code> 个元素（及下标）加入到优先队列中</p>
</li>
<li>
<p>遍历 <code>nums</code> 数组元素下标 <code>i</code> （从第 <code>k</code> 位元素开始），即，窗口的右边界</p>
<ul>
<li>将 <code>(nums[i], i)</code> 加入到 <code>que</code> 中</li>
<li>若 <code>que</code> 根节点所对应的数组元素下标（即， <code>que.top().second</code> ） 小于 窗口的左边界（即， <code>i - k + 1</code> ），则这个最大值不在窗口范围内，而是在窗口左侧，将其从 <code>que</code> 中移除</li>
<li>将 <code>que</code> 根节点所对应的数组元素（即， <code>que.top().first</code> ）加入到目标数组中</li>
</ul>
</li>
</ol>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token function">maxSlidingWindow</span><span class="token punctuation">(</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&</span> nums<span class="token punctuation">,</span> <span class="token keyword">int</span> k<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> priority_queue<span class="token operator"><</span>pair<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">>></span> que<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token function">res</span><span class="token punctuation">(</span>nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">-</span> k <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token comment">// 将前 k 个元素添加到优先队列</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> k<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="6"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">emplace</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> i<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token comment">// 将当前窗口最大值添加到目标数组</span></pre></td></tr><tr><td data-num="8"></td><td><pre> res<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> que<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>first<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> k<span class="token punctuation">;</span> i <span class="token operator"><</span> nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token comment">// 将当前元素添加到优先队列</span></pre></td></tr><tr><td data-num="11"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">emplace</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> i<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token comment">// 当前队列的最大值不在窗口内，将其移除</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>que<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>second <span class="token operator"><</span> i <span class="token operator">-</span> k <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="14"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token comment">// 将当前窗口最大值添加到目标数组</span></pre></td></tr><tr><td data-num="16"></td><td><pre> res<span class="token punctuation">[</span>i <span class="token operator">-</span> k <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> que<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>first<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token keyword">return</span> res<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="19"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mi>log</mi><mo></mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n \log{n})</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord"><span class="mord mathnormal">n</span></span><span class="mclose">)</span></span></span></span> ，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 是数组 <code>nums</code> 的长度</p>
<ul>
<li>遍历数组的时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></li>
<li>将元素添加到优先队列的时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>log</mi><mo></mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\log{n})</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord"><span class="mord mathnormal">n</span></span><span class="mclose">)</span></span></span></span> （在最坏情况下，数组 <code>nums</code> 中的元素单调递增，优先队列中包含了所有元素）</li>
</ul>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span> ，这里仅考虑了优先队列所需空间，忽略了目标数组所需空间</p>
<p>参考</p>
<ul>
<li><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/sliding-window-maximum/solution/dong-hua-yan-shi-dan-diao-dui-lie-239hua-hc5u/">力扣官方题解：滑动窗口最大值</a></li>
<li><a target="_blank" rel="noopener" href="http://www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue">cplusplus：std::priority_queue</a></li>
</ul>
<h2 id="method-2-单调队列"><a class="anchor" href="#method-2-单调队列">#</a> Method 2: 单调队列</h2>
<p>双向队列：队列的两端都可以 入队 / 出队</p>
<p>单调队列：从队首到队尾，元素单调递减，或递增</p>
<p>本题可定义一个 元素单调递减的单调队列 ，以维护窗口内的最大值（即，队列的首端元素为队列最大值）</p>
<ul>
<li>若队首元素不在窗口内（即，对应数组下标小于窗口左边界），将其移除</li>
<li>若队首元素在窗口内，则该元素即为窗口内元素的最大值</li>
</ul>
<p>为实现队列元素的单调递减，我们在添加元素时，需做以下考虑：</p>
<ul>
<li>若队列尾端元素小于等于当前元素，则将队尾元素移除（因为队尾元素对应的数组下标在当前元素的左侧，当队尾元素小于当前元素时，其不可能成为当前窗口及后续滑动窗口的最大值，可将其从队列中永久移除）</li>
<li>直到队列尾端元素大于当前元素时，才将当前元素添加到队列中</li>
</ul>
<p>算法流程：</p>
<ol>
<li>定义一个双向队列： <code>deque<int> que;</code> ，用以实现单调队列</li>
<li>遍历数组 <code>nums</code> 数组元素下标，定义为窗口的右边界 <code>right</code>
<ul>
<li>若队列不为空且当前元素大于等于队尾元素，将队尾元素移除，直到队列为空或当前元素小于新的队尾元素</li>
<li>将当前元素添加到队尾</li>
<li>若队首元素的下标小于滑动窗口左侧边界，将其从队首移除，直到队首元素在窗口中为止</li>
<li>若长为 <code>k</code> 的窗口已形成（即， <code>right >= k - 1</code> ），则将窗口最大值（即，队首元素）添加到目标数组</li>
</ul>
</li>
</ol>
<blockquote>
<p>特别地，为便于操作，我们可将数组元素的下标存放在队列中</p>
</blockquote>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token function">maxSlidingWindow</span><span class="token punctuation">(</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&</span> nums<span class="token punctuation">,</span> <span class="token keyword">int</span> k<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> deque<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> que<span class="token punctuation">;</span> <span class="token comment">// 单调队列（从队首到队尾，元素单调递减）</span></pre></td></tr><tr><td data-num="3"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> res<span class="token punctuation">;</span> <span class="token comment">// 目标数组</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> left <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> right <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> right <span class="token operator"><</span> nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> right<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token comment">// 队列不为空且当前考察元素大于等于队尾元素，将队尾元素移除</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>que<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&&</span> nums<span class="token punctuation">[</span>que<span class="token punctuation">.</span><span class="token function">back</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">]</span> <span class="token operator"><=</span> nums<span class="token punctuation">[</span>right<span class="token punctuation">]</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="7"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">pop_back</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token comment">// 将当前元素的下标添加到队尾</span></pre></td></tr><tr><td data-num="9"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>right<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token comment">// 窗口左边界</span></pre></td></tr><tr><td data-num="11"></td><td><pre> left <span class="token operator">=</span> right <span class="token operator">-</span> k <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token comment">// 将小于 left 的元素下标从队列移除</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>que<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator"><</span> left<span class="token punctuation">)</span></pre></td></tr><tr><td data-num="14"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">pop_front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token comment">// 队列首端对应元素就是窗口最大值</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>right <span class="token operator">>=</span> k <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="17"></td><td><pre> res<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>nums<span class="token punctuation">[</span>que<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="19"></td><td><pre> <span class="token keyword">return</span> res<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 为数组长度</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(k)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mclose">)</span></span></span></span>，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span></span></span></span> 为窗口长度</p>
<ul>
<li>队列最多有 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">k + 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7778em;vertical-align:-0.0833em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span> 个元素，故，队列所需空间为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(k)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mclose">)</span></span></span></span></li>
<li>忽略了目标数组所需空间</li>
</ul>
<p>参考：</p>
<ul>
<li><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/sliding-window-maximum/solution/dong-hua-yan-shi-dan-diao-dui-lie-239hua-hc5u/">力扣官方题解：滑动窗口最大值</a></li>
<li><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/sliding-window-maximum/solution/dong-hua-yan-shi-dan-diao-dui-lie-239hua-hc5u/">编程狂想曲：动画演示 单调队列 239. 滑动窗口最大值</a></li>
<li><a target="_blank" rel="noopener" href="http://www.cplusplus.com/reference/deque/deque/">cplusplus：std::deque</a></li>
</ul>
<h1 id="leetcode-347-前-k-个高频元素"><a class="anchor" href="#leetcode-347-前-k-个高频元素">#</a> LeetCode 347. 前 K 个高频元素</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/top-k-frequent-elements/">347. Top K Frequent Elements</a></p>
<p>给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code> ，请你返回其中出现频率前 <code>k</code> 高的元素。你可以按 <strong>任意顺序</strong> 返回答案。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：nums = [1], k = 1
输出：[1]
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo></mrow><annotation encoding="application/x-tex">1 \le</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span></span></span></span> <code>nums.length</code> <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">\le 10^5</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">5</span></span></span></span></span></span></span></span></span></span></span></li>
<li><code>k</code> 的取值范围是 <code>[1, 数组中不相同的元素的个数]</code></li>
<li>题目数据保证答案唯一，换句话说，数组中前 <code>k</code> 个高频元素的集合是唯一的</li>
</ul>
<p><strong>进阶</strong>：你所设计算法的时间复杂度 必须 优于 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mi>log</mi><mo></mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n \log n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span> ，其中 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 是数组大小。</p>
<h2 id="思路-7"><a class="anchor" href="#思路-7">#</a> 思路</h2>
<p>解题基本思路：</p>
<ul>
<li>统计元素出现频率：利用 <strong>哈希 map</strong> 来统计数组中各元素出现的次数</li>
<li>对频率排序：利用 <strong>优先级队列</strong> 来对频率进行排序</li>
<li>根据排序结果找出前 K 个高频元素</li>
</ul>
<p>题目只需找出前 K 个高频元素，因此可采用固定大小为 K 的 优先级队列 维护一个长为 K 的有序序列即可，而无需采用 vector 容器对所有元素的频次进行排序</p>
<p>由于优先级队列（堆）只能移除队首元素，本题采用 <strong>最小化堆（小顶堆）</strong> ，以便移除频次最少的元素</p>
<p>最小化堆的定义：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">class</span> <span class="token class-name">comp</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">public</span><span class="token operator">:</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">bool</span> <span class="token keyword">operator</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">(</span><span class="token keyword">const</span> pair<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">&</span>LHS<span class="token punctuation">,</span> <span class="token keyword">const</span> pair<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">&</span>RHS<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">return</span> LHS<span class="token punctuation">.</span>second <span class="token operator">></span> RHS<span class="token punctuation">.</span>second<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="6"></td><td><pre><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre></pre></td></tr><tr><td data-num="8"></td><td><pre>priority_queue<span class="token operator"><</span>pair<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span><span class="token punctuation">,</span> vector<span class="token operator"><</span>pair<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">>></span><span class="token punctuation">,</span> comp<span class="token operator">></span> que<span class="token punctuation">;</span></pre></td></tr></tbody></table></figure><blockquote>
<p>对于堆， <code>LHS.second > RHS.second</code> 建立的是小顶堆， <code>LHS.second < RHS.second</code> 建立的是大顶堆</p>
<p>对于 <code>sort</code> 函数， <code>LHS.second > RHS.second</code> 得到的是降序排列， <code>LHS.second < RHS.second</code> 得到的是升序排列</p>
</blockquote>
<h2 id="method-哈希-map-优先级队列"><a class="anchor" href="#method-哈希-map-优先级队列">#</a> Method: 哈希 map + 优先级队列</h2>
<p>算法思路：</p>
<p>定义一个哈希表（ <code>unordered_map</code> ），用于统计数组元素的出现频次，其中，key 为元素值，value 为频次</p>
<p>定义一个优先级队列，遍历哈希表：</p>
<ul>
<li>将哈希表的键值对添加到队列</li>
<li>若队列长度大于 K ，则从队列中移除频次最少的元素</li>
</ul>
<p>从优先级队列中提取出前 K 个高频元素的元素值，将其填充到目标数组中</p>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 最小化堆的比较函数</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">class</span> <span class="token class-name">comp</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="3"></td><td><pre><span class="token keyword">public</span><span class="token operator">:</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">bool</span> <span class="token keyword">operator</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">(</span><span class="token keyword">const</span> pair<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">&</span>LHS<span class="token punctuation">,</span> <span class="token keyword">const</span> pair<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> <span class="token operator">&</span>RHS<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">return</span> LHS<span class="token punctuation">.</span>second <span class="token operator">></span> RHS<span class="token punctuation">.</span>second<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="7"></td><td><pre><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre></pre></td></tr><tr><td data-num="9"></td><td><pre><span class="token keyword">class</span> <span class="token class-name">Solution</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="10"></td><td><pre><span class="token keyword">public</span><span class="token operator">:</span></pre></td></tr><tr><td data-num="11"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token function">topKFrequent</span><span class="token punctuation">(</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&</span> nums<span class="token punctuation">,</span> <span class="token keyword">int</span> k<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token comment">// 统计数字出现的频次</span></pre></td></tr><tr><td data-num="13"></td><td><pre> unordered_map<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span> hash<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> nums<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="15"></td><td><pre> hash<span class="token punctuation">[</span>nums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token operator">++</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token comment">// 利用固定大小为 K 的优先队列扫描哈希表</span></pre></td></tr><tr><td data-num="17"></td><td><pre> priority_queue<span class="token operator"><</span>pair<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">></span><span class="token punctuation">,</span> vector<span class="token operator"><</span>pair<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">>></span><span class="token punctuation">,</span> comp<span class="token operator">></span> que<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">auto</span> it <span class="token operator">=</span> hash<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> it <span class="token operator">!=</span> hash<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> it<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="19"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token operator">*</span>it<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>que<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">></span> k<span class="token punctuation">)</span></pre></td></tr><tr><td data-num="21"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="23"></td><td><pre> <span class="token comment">// 提取出前 K 个高频元素（升序填充到目标数组）</span></pre></td></tr><tr><td data-num="24"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token function">res</span><span class="token punctuation">(</span>k<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> k<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="26"></td><td><pre> res<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> que<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>first<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="27"></td><td><pre> que<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="28"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="29"></td><td><pre> <span class="token keyword">return</span> res<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="30"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="31"></td><td><pre><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mi>log</mi><mo></mo><mi>k</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n \log{k})</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.03148em;">k</span></span><span class="mclose">)</span></span></span></span> ，其中，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 为数组长度，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span></span></span></span> 为输出高频元素数</p>
<ul>
<li>遍历哈希表的最坏时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></li>
<li>优先级队列的入队 / 出队时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>log</mi><mo></mo><mi>k</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\log{k})</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.03148em;">k</span></span><span class="mclose">)</span></span></span></span></li>
</ul>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<p>参考：</p>
<ul>
<li><a target="_blank" rel="noopener" href="http://www.cplusplus.com/reference/queue/priority_queue/">cplusplus：std::priority_queue</a></li>
<li><a target="_blank" rel="noopener" href="https://www.programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html">代码随想录：前 K 个高频元素</a></li>
</ul>
<h1 id="leetcode-394-字符串解码"><a class="anchor" href="#leetcode-394-字符串解码">#</a> LeetCode 394. 字符串解码</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/decode-string/">394. Decode String</a></p>
<p>给定一个经过编码的字符串，返回它解码后的字符串。</p>
<p>编码规则为: <code>k[encoded_string]</code> ，表示其中方括号内部的 <code>encoded_string</code> 正好重复 <code>k</code> 次。注意 <code>k</code> 保证为正整数。</p>
<p>你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。</p>
<p>此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 <code>k</code> ，例如不会出现像 <code>3a</code> 或 <code>2[4]</code> 的输入。</p>
<p><strong>示例 1：</strong></p>
<pre><code>输入：s = "3[a]2[bc]"
输出："aaabcbc"
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：s = "3[a2[c]]"
输出："accaccacc"
</code></pre>
<p><strong>示例 3：</strong></p>
<pre><code>输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li><code>1 <= s.length <= 30</code></li>
<li><code>s</code> 由小写英文字母、数字和方括号 <code>'[]'</code> 组成</li>
<li><code>s</code> 保证是一个 <strong>有效</strong> 的输入</li>
<li><code>s</code> 中所有整数的取值范围为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">[</mo><mn>1</mn><mo separator="true">,</mo><mn>300</mn><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">[1, 300]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">1</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">300</span><span class="mclose">]</span></span></span></span></li>
</ul>
<h2 id="method-1-栈-2"><a class="anchor" href="#method-1-栈-2">#</a> Method 1: 栈</h2>
<p>算法思路：</p>
<p>利用一个栈来维护字符串中的字母、数字和括号</p>
<p>遍历字符串 s ：</p>
<ul>
<li>如果当前的字符为数位，解析出一个数字（连续的多个数位）并进栈</li>
<li>如果当前的字符为字母或者左括号，直接进栈</li>
<li>如果当前的字符为右括号，开始出栈，一直到左括号出栈，将出栈序列拼接成一个字符串；然后再取出栈顶的数字（即，字符串重复出现的次数），根据这个数字和字符串构造新字符串并进栈</li>
</ul>
<blockquote>
<p>为便于拼接目标字符串，可以用 vector 容器来模拟栈操作，具体可参考 <a target="_blank" rel="noopener" href="https://leetcode.cn/problems/decode-string/solution/zi-fu-chuan-jie-ma-by-leetcode-solution/">leetcode-solution</a></p>
</blockquote>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>string <span class="token function">decodeString</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> string res <span class="token operator">=</span> <span class="token string">""</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre> stack<span class="token operator"><</span>string<span class="token operator">></span> stk<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">int</span> ptr <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>ptr <span class="token operator"><</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">char</span> cur <span class="token operator">=</span> s<span class="token punctuation">[</span>ptr<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">isdigit</span><span class="token punctuation">(</span>cur<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 将数字（重复次数）入栈</span></pre></td></tr><tr><td data-num="9"></td><td><pre> string digit <span class="token operator">=</span> <span class="token string">""</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token function">isdigit</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>ptr<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 解析数字</span></pre></td></tr><tr><td data-num="11"></td><td><pre> digit<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>ptr<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token operator">++</span>ptr<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>digit<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">isalpha</span><span class="token punctuation">(</span>cur<span class="token punctuation">)</span> <span class="token operator">||</span> cur <span class="token operator">==</span> <span class="token char">'['</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 将字母和左括号入栈</span></pre></td></tr><tr><td data-num="16"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token function">string</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span> cur<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token operator">++</span>ptr<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> <span class="token comment">// 遇到右括号，将与之匹配的左括号及括号中间的字符出栈</span></pre></td></tr><tr><td data-num="19"></td><td><pre> string tmp <span class="token operator">=</span> <span class="token string">""</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>stk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">!=</span> <span class="token string">"["</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 解析当前括号对所包围的子串</span></pre></td></tr><tr><td data-num="21"></td><td><pre> tmp <span class="token operator">+=</span> stk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="22"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="23"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="24"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 出栈：左括号</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token keyword">int</span> repNum <span class="token operator">=</span> <span class="token function">stoi</span><span class="token punctuation">(</span>stk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 子串的重复次数</span></pre></td></tr><tr><td data-num="26"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 出栈：重复次数</span></pre></td></tr><tr><td data-num="27"></td><td><pre> string str <span class="token operator">=</span> <span class="token string">""</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="28"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>repNum<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token comment">// 根据重复次数 repNum 和子串 tmp 解码字符串（例如，由 3 和 a 得到 aaa）</span></pre></td></tr><tr><td data-num="29"></td><td><pre> str <span class="token operator">+=</span> tmp<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="30"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>stk<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 无嵌套情形，可直接将 str 反转然后添加到目标字符串</span></pre></td></tr><tr><td data-num="31"></td><td><pre> <span class="token function">reverse</span><span class="token punctuation">(</span>str<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> str<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="32"></td><td><pre> res <span class="token operator">+=</span> str<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="33"></td><td><pre> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> <span class="token comment">// 可能存在嵌套（例如 "3 [a2 [c]]"），或者前面有有效字符（例如 "2 [abc] ef3 [cd]"）</span></pre></td></tr><tr><td data-num="34"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>str<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="35"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="36"></td><td><pre> <span class="token operator">++</span>ptr<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="37"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="38"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="39"></td><td><pre></pre></td></tr><tr><td data-num="40"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>stk<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 连接栈内剩余元素，将其反转后添加到目标字符串</span></pre></td></tr><tr><td data-num="41"></td><td><pre> string tmp <span class="token operator">=</span> <span class="token string">""</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="42"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>stk<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="43"></td><td><pre> tmp <span class="token operator">+=</span> stk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="44"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="45"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="46"></td><td><pre> <span class="token function">reverse</span><span class="token punctuation">(</span>tmp<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">,</span> tmp<span class="token punctuation">.</span><span class="token function">end</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="47"></td><td><pre> res <span class="token operator">+=</span> tmp<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="48"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="49"></td><td><pre></pre></td></tr><tr><td data-num="50"></td><td><pre> <span class="token keyword">return</span> res<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="51"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi mathvariant="normal">∣</mi><mi>s</mi><mi mathvariant="normal">∣</mi><mo>+</mo><mi mathvariant="normal">∣</mi><mi>S</mi><mi mathvariant="normal">∣</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\vert s \vert + \vert S \vert)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">∣</span><span class="mord mathnormal">s</span><span class="mord">∣</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">∣</span><span class="mord mathnormal" style="margin-right:0.05764em;">S</span><span class="mord">∣</span><span class="mclose">)</span></span></span></span>，其中 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">∣</mi><mi>s</mi><mi mathvariant="normal">∣</mi></mrow><annotation encoding="application/x-tex">\vert s \vert</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">∣</span><span class="mord mathnormal">s</span><span class="mord">∣</span></span></span></span> 是原字符串 s 的长度，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">∣</mi><mi>S</mi><mi mathvariant="normal">∣</mi></mrow><annotation encoding="application/x-tex">\vert S \vert</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">∣</span><span class="mord mathnormal" style="margin-right:0.05764em;">S</span><span class="mord">∣</span></span></span></span> 是解码后得出的字符串 S 的长度</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi mathvariant="normal">∣</mi><mi>s</mi><mi mathvariant="normal">∣</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\vert s \vert)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">∣</span><span class="mord mathnormal">s</span><span class="mord">∣</span><span class="mclose">)</span></span></span></span></p>
<h2 id="method-2-递归"><a class="anchor" href="#method-2-递归">#</a> Method 2: 递归</h2>
<p>算法思路：</p>
<p>定义递归函数，从左向右解析字符串 s ：</p>
<ul>
<li>如果当前位置为数字位，后面一定包含一个用方括号表示的字符串，此时可采取以下操作：
<ul>
<li>先解析出一个数字 repNum</li>
<li>然后解析左括号</li>
<li>递归解析后面的内容，遇到对应的右括号就返回，得到字母序列 str</li>
<li>根据字母序列 str 以及重复的次数 repNum 构造新的字符串</li>
</ul>
</li>
<li>如果当前位置是字母位，可直接解析当前字母，然后递归解析后面内容</li>
</ul>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">int</span> <span class="token function">getDigits</span><span class="token punctuation">(</span>string<span class="token operator">&</span> s<span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">&</span> ptr<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 从 ptr 位开始提取数字</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">int</span> num <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>ptr <span class="token operator"><</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&&</span> <span class="token function">isdigit</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>ptr<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="4"></td><td><pre> num <span class="token operator">=</span> num <span class="token operator">*</span> <span class="token number">10</span> <span class="token operator">+</span> <span class="token punctuation">(</span>s<span class="token punctuation">[</span>ptr<span class="token punctuation">]</span> <span class="token operator">-</span> <span class="token char">'0'</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token operator">++</span>ptr<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">return</span> num<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="9"></td><td><pre></pre></td></tr><tr><td data-num="10"></td><td><pre>string <span class="token function">getString</span><span class="token punctuation">(</span>string<span class="token operator">&</span> s<span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token operator">&</span> ptr<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>ptr <span class="token operator">==</span> s<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">||</span> s<span class="token punctuation">[</span>ptr<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token char">']'</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token string">""</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre> string res <span class="token operator">=</span> <span class="token string">""</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">isdigit</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>ptr<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token keyword">int</span> repNum <span class="token operator">=</span> <span class="token function">getDigits</span><span class="token punctuation">(</span>s<span class="token punctuation">,</span> ptr<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 解析 Digits</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token operator">++</span>ptr<span class="token punctuation">;</span> <span class="token comment">// 过滤左括号</span></pre></td></tr><tr><td data-num="16"></td><td><pre> string str <span class="token operator">=</span> <span class="token function">getString</span><span class="token punctuation">(</span>s<span class="token punctuation">,</span> ptr<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 解析 String</span></pre></td></tr><tr><td data-num="17"></td><td><pre> <span class="token operator">++</span>ptr<span class="token punctuation">;</span> <span class="token comment">// 过滤右括号</span></pre></td></tr><tr><td data-num="18"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span>repNum<span class="token operator">--</span><span class="token punctuation">)</span> res <span class="token operator">+=</span> str<span class="token punctuation">;</span> <span class="token comment">// 构造目标字符串</span></pre></td></tr><tr><td data-num="19"></td><td><pre> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token function">isalpha</span><span class="token punctuation">(</span>s<span class="token punctuation">[</span>ptr<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="20"></td><td><pre> res <span class="token operator">=</span> <span class="token function">string</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">,</span> s<span class="token punctuation">[</span>ptr<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 解析 Char</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token operator">++</span>ptr<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="23"></td><td><pre> <span class="token keyword">return</span> res <span class="token operator">+</span> <span class="token function">getString</span><span class="token punctuation">(</span>s<span class="token punctuation">,</span> ptr<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="24"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="25"></td><td><pre></pre></td></tr><tr><td data-num="26"></td><td><pre>string <span class="token function">decodeString</span><span class="token punctuation">(</span>string s<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="27"></td><td><pre> <span class="token keyword">int</span> ptr <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="28"></td><td><pre> string ans <span class="token operator">=</span> <span class="token function">getString</span><span class="token punctuation">(</span>s<span class="token punctuation">,</span> ptr<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="29"></td><td><pre> <span class="token keyword">return</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="30"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi mathvariant="normal">∣</mi><mi>s</mi><mi mathvariant="normal">∣</mi><mo>+</mo><mi mathvariant="normal">∣</mi><mi>S</mi><mi mathvariant="normal">∣</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\vert s \vert + \vert S \vert)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">∣</span><span class="mord mathnormal">s</span><span class="mord">∣</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">∣</span><span class="mord mathnormal" style="margin-right:0.05764em;">S</span><span class="mord">∣</span><span class="mclose">)</span></span></span></span>，其中 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">∣</mi><mi>s</mi><mi mathvariant="normal">∣</mi></mrow><annotation encoding="application/x-tex">\vert s \vert</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">∣</span><span class="mord mathnormal">s</span><span class="mord">∣</span></span></span></span> 是原字符串 s 的长度，<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="normal">∣</mi><mi>S</mi><mi mathvariant="normal">∣</mi></mrow><annotation encoding="application/x-tex">\vert S \vert</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">∣</span><span class="mord mathnormal" style="margin-right:0.05764em;">S</span><span class="mord">∣</span></span></span></span> 是解码后得出的字符串 S 的长度</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi mathvariant="normal">∣</mi><mi>s</mi><mi mathvariant="normal">∣</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\vert s \vert)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">∣</span><span class="mord mathnormal">s</span><span class="mord">∣</span><span class="mclose">)</span></span></span></span>，只考虑递归使用的栈空间，不考虑答案所占空间</p>
<p>参考：<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/decode-string/solution/zi-fu-chuan-jie-ma-by-leetcode-solution/">leetcode-solution</a></p>
<h1 id="leetcode-85-最大矩形"><a class="anchor" href="#leetcode-85-最大矩形">#</a> LeetCode 85. 最大矩形</h1>
<p><a target="_blank" rel="noopener" href="https://leetcode.cn/problems/maximal-rectangle/">85. Maximal Rectangle</a></p>
<p>给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。</p>
<p><strong>示例 1：</strong></p>
<p><img loading="lazy" data-src="LeetCode-%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E4%B8%93%E9%A2%98/LeetCode85_Example1.webp" alt="" height="200px"></p>
<pre><code>输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。
</code></pre>
<p><strong>示例 2：</strong></p>
<pre><code>输入：matrix = [["0"]]
输出：0
</code></pre>
<p><strong>示例 3：</strong></p>
<pre><code>输入：matrix = [["1"]]
输出：1
</code></pre>
<p><strong>提示：</strong></p>
<ul>
<li>rows == matrix.length</li>
<li>cols == matrix[i].length</li>
<li>1 <= row, cols <= 200</li>
<li>matrix [i][j] 为 '0' 或 '1'</li>
</ul>
<h2 id="method-栈-3"><a class="anchor" href="#method-栈-3">#</a> Method: 栈</h2>
<p>算法思路：</p>
<p>可以将矩阵拆分成一系列的柱状图，为了计算矩形的最大面积，我们需要计算每个柱状图中的最大矩形面积，并从所有柱状图中找到全局最大值</p>
<p>定义 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">m</span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 分别表示矩阵 matrix 的行数和列数，因此可将矩阵拆分成 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">m</span></span></span></span> 个柱状图</p>
<p>特别地，第 i 个柱状图的范围为矩阵第 0 行至第 i 行，即，matrix [0] 至 matrix [i] ，在该柱状图中，第 j 个柱子的高度为 height [i][j]</p>
<ul>
<li>height [i][j] 表示从 (i, 0) 位置开始往下数、以 (i, j) 位置结尾的连续 1 的个数</li>
</ul>
<p>其中，某柱状图中的最大矩形面积，可按照 <strong>LeetCode 84. 柱状图中最大的矩形</strong> 中的思路求解</p>
<p>通过遍历 i（即，遍历 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">m</span></span></span></span> 个柱状图），求出每一个柱状图的最大矩形面积，即可得出所有柱状图中的最大矩形（即，矩阵中的最大矩形面积）</p>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">int</span> <span class="token function">maximalRectangle</span><span class="token punctuation">(</span>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">char</span><span class="token operator">>></span><span class="token operator">&</span> matrix<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">int</span> m <span class="token operator">=</span> matrix<span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">int</span> n <span class="token operator">=</span>matrix<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span><span class="token function">size</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token comment">// 预处理，计算每一个柱状图中的每一个柱子高度</span></pre></td></tr><tr><td data-num="6"></td><td><pre> vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span> <span class="token function">height</span><span class="token punctuation">(</span>m<span class="token punctuation">,</span> <span class="token generic-function"><span class="token function">vector</span><span class="token generic class-name"><span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span></span></span><span class="token punctuation">(</span>n<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> m<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator"><</span> n<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>matrix<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token char">'1'</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="10"></td><td><pre> height<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> i <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">?</span> <span class="token number">1</span> <span class="token operator">:</span> height<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// 矩阵中的最大矩形面积</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> m<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 遍历 m 个柱状图，计算每个柱状图的最大矩形面积</span></pre></td></tr><tr><td data-num="17"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token function">left</span><span class="token punctuation">(</span>n<span class="token punctuation">,</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//left [j] 表示以 height [j] 为高的矩形的左边界</span></pre></td></tr><tr><td data-num="18"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token function">right</span><span class="token punctuation">(</span>n<span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//right [j] 表示以 height [j] 为高的矩形的矩形的右边界</span></pre></td></tr><tr><td data-num="19"></td><td><pre> stack<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> stk<span class="token punctuation">;</span> <span class="token comment">// 单调栈</span></pre></td></tr><tr><td data-num="20"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator"><</span> n<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 维护单调栈，并更新 left 和 right 数组</span></pre></td></tr><tr><td data-num="21"></td><td><pre> <span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token operator">!</span>stk<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">&&</span> height<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>stk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">]</span> <span class="token operator">>=</span> height<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="22"></td><td><pre> right<span class="token punctuation">[</span>stk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">]</span> <span class="token operator">=</span> j<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="23"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="24"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>stk<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> left<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> stk<span class="token punctuation">.</span><span class="token function">top</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="26"></td><td><pre> stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span>j<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="27"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="28"></td><td><pre> <span class="token keyword">int</span> area <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// 第 i 个柱形图的最大矩形面积</span></pre></td></tr><tr><td data-num="29"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator"><</span> n<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="30"></td><td><pre> area <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>area<span class="token punctuation">,</span> height<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">*</span> <span class="token punctuation">(</span>right<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">-</span> left<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="31"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="32"></td><td><pre> ans <span class="token operator">=</span> <span class="token function">max</span><span class="token punctuation">(</span>ans<span class="token punctuation">,</span> area<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 更新矩阵的最大矩形面积</span></pre></td></tr><tr><td data-num="33"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="34"></td><td><pre> <span class="token keyword">return</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="35"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>m</mi><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(m n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">mn</span><span class="mclose">)</span></span></span></span>，其中 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>m</mi></mrow><annotation encoding="application/x-tex">m</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">m</span></span></span></span> 和 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 分别为矩阵 matrix 的行数和列数</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>m</mi><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(m n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">mn</span><span class="mclose">)</span></span></span></span></p>
<p>参考：<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/maximal-rectangle/solution/zui-da-ju-xing-by-leetcode-solution-bjlu/">leetcode-solution</a></p>
<div class="tags"><a href="/tags/%E9%98%9F%E5%88%97/" rel="tag"><i class="ic i-tag"></i>队列</a><a href="/tags/%E6%A0%88/" rel="tag"><i class="ic i-tag"></i>栈</a></div></div><footer><div class="meta"><span class="item"><span class="icon"><i class="ic i-calendar-check"></i></span><span class="text">更新于</span><time title="修改时间：2024-06-08 23:08:50" itemprop="dateModified" datetime="2024-06-08T23:08:50+08:00">2024-06-08</time></span></div><div id="copyright"><ul><li class="author"><strong>本文作者：</strong>Jiankychen<i class="ic i-at"><em>@</em></i>Jiankychen's Blog</li><li class="link"><strong>本文链接：</strong><a href="https://jiankychen.github.io/leetcode-stacks&queues.html" title="LeetCode - 栈与队列专题">https://jiankychen.github.io/leetcode-stacks&queues.html</a></li><li class="license"><strong>版权声明：</strong>本站所有文章除特别声明外，均采用 <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh"><i class="ic i-creative-commons"><em>(CC)</em></i>BY-NC-SA</a> 许可协议。转载请注明出处！</li></ul></div></footer></article></div><div class="post-nav"><div class="item left"><a href="/KMP.html" rel="prev" itemprop="url" data-background-image="https://img.timelessq.com/images/2022/07/26/a1f3404a5032323ea4857ac5a6354d2f.jpg" title="KMP 算法"><span class="type">上一篇</span><span class="category"><i class="ic i-flag"></i>Data Structure</span><h3>KMP 算法</h3></a></div><div class="item right"><a href="/leetcode-binarytree.html" rel="next" itemprop="url" data-background-image="https://i.imgtg.com/2023/03/09/YQSYM.jpg" title="LeetCode - 二叉树专题"><span class="type">下一篇</span><span class="category"><i class="ic i-flag"></i>Coding</span><h3>LeetCode - 二叉树专题</h3></a></div></div><div class="wrap" id="comments"></div></div><div id="sidebar"><div class="inner"><div class="panels"><div class="inner"><div class="contents panel pjax" data-title="文章目录"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-1047-%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9"><span class="toc-number">1.</span> <span class="toc-text"> LeetCode 1047. 删除字符串中的所有相邻重复项</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF"><span class="toc-number">1.1.</span> <span class="toc-text"> 思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-1-%E6%A0%88"><span class="toc-number">1.2.</span> <span class="toc-text"> Method 1: 栈</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-2-%E5%AD%97%E7%AC%A6%E4%B8%B2"><span class="toc-number">1.3.</span> <span class="toc-text"> Method 2: 字符串</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-150-%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC"><span class="toc-number">2.</span> <span class="toc-text"> LeetCode 150. 逆波兰表达式求值</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF-2"><span class="toc-number">2.1.</span> <span class="toc-text"> 思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-%E6%A0%88"><span class="toc-number">2.2.</span> <span class="toc-text"> Method: 栈</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-155-%E6%9C%80%E5%B0%8F%E6%A0%88"><span class="toc-number">3.</span> <span class="toc-text"> LeetCode 155. 最小栈</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#method-%E8%BE%85%E5%8A%A9%E6%A0%88"><span class="toc-number">3.1.</span> <span class="toc-text"> Method: 辅助栈</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-20-%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7"><span class="toc-number">4.</span> <span class="toc-text"> LeetCode 20. 有效的括号</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF-3"><span class="toc-number">4.1.</span> <span class="toc-text"> 思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-1-%E6%A0%88-map"><span class="toc-number">4.2.</span> <span class="toc-text"> Method 1: 栈 + map</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-2-%E6%A0%88"><span class="toc-number">4.3.</span> <span class="toc-text"> Method 2: 栈</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-225-%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88"><span class="toc-number">5.</span> <span class="toc-text"> LeetCode 225. 用队列实现栈</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF-4"><span class="toc-number">5.1.</span> <span class="toc-text"> 思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-%E4%B8%A4%E4%B8%AA%E9%98%9F%E5%88%97"><span class="toc-number">5.2.</span> <span class="toc-text"> Method: 两个队列</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-%E4%B8%80%E4%B8%AA%E9%98%9F%E5%88%97"><span class="toc-number">5.3.</span> <span class="toc-text"> Method: 一个队列</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-227-%E5%9F%BA%E6%9C%AC%E8%AE%A1%E7%AE%97%E5%99%A8-ii"><span class="toc-number">6.</span> <span class="toc-text"> LeetCode 227. 基本计算器 II</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#method-%E6%A0%88-2"><span class="toc-number">6.1.</span> <span class="toc-text"> Method: 栈</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E6%80%9D%E8%B7%AF"><span class="toc-number">6.2.</span> <span class="toc-text"> 算法思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E6%B5%81%E7%A8%8B"><span class="toc-number">6.3.</span> <span class="toc-text"> 算法流程</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="toc-number">6.4.</span> <span class="toc-text"> 代码实现</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90"><span class="toc-number">6.5.</span> <span class="toc-text"> 复杂度分析</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%82%E8%80%83%E8%B5%84%E6%96%99"><span class="toc-number">6.6.</span> <span class="toc-text"> 参考资料</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-232-%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97"><span class="toc-number">7.</span> <span class="toc-text"> LeetCode 232. 用栈实现队列</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF-5"><span class="toc-number">7.1.</span> <span class="toc-text"> 思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method"><span class="toc-number">7.2.</span> <span class="toc-text"> Method</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-239-%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC"><span class="toc-number">8.</span> <span class="toc-text"> LeetCode 239. 滑动窗口最大值</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF-6"><span class="toc-number">8.1.</span> <span class="toc-text"> 思路：</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-1-%E4%BC%98%E5%85%88%E9%98%9F%E5%88%97"><span class="toc-number">8.2.</span> <span class="toc-text"> Method 1: 优先队列</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-2-%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97"><span class="toc-number">8.3.</span> <span class="toc-text"> Method 2: 单调队列</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-347-%E5%89%8D-k-%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0"><span class="toc-number">9.</span> <span class="toc-text"> LeetCode 347. 前 K 个高频元素</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%80%9D%E8%B7%AF-7"><span class="toc-number">9.1.</span> <span class="toc-text"> 思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-%E5%93%88%E5%B8%8C-map-%E4%BC%98%E5%85%88%E7%BA%A7%E9%98%9F%E5%88%97"><span class="toc-number">9.2.</span> <span class="toc-text"> Method: 哈希 map + 优先级队列</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-394-%E5%AD%97%E7%AC%A6%E4%B8%B2%E8%A7%A3%E7%A0%81"><span class="toc-number">10.</span> <span class="toc-text"> LeetCode 394. 字符串解码</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#method-1-%E6%A0%88-2"><span class="toc-number">10.1.</span> <span class="toc-text"> Method 1: 栈</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#method-2-%E9%80%92%E5%BD%92"><span class="toc-number">10.2.</span> <span class="toc-text"> Method 2: 递归</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#leetcode-85-%E6%9C%80%E5%A4%A7%E7%9F%A9%E5%BD%A2"><span class="toc-number">11.</span> <span class="toc-text"> LeetCode 85. 最大矩形</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#method-%E6%A0%88-3"><span class="toc-number">11.1.</span> <span class="toc-text"> Method: 栈</span></a></li></ol></li></ol></div><div class="related panel pjax" data-title="系列文章"><ul><li><a href="/leetcode-binarysearch.html" rel="bookmark" title="LeetCode - 二分查找专题">LeetCode - 二分查找专题</a></li><li><a href="/leetcode-vectors.html" rel="bookmark" title="LeetCode - 数组专题">LeetCode - 数组专题</a></li><li><a href="/leetcode-list.html" rel="bookmark" title="LeetCode - 链表专题">LeetCode - 链表专题</a></li><li><a href="/leetcode-hashtable.html" rel="bookmark" title="LeetCode - 哈希表专题">LeetCode - 哈希表专题</a></li><li><a href="/leetcode-string.html" rel="bookmark" title="LeetCode - 字符串专题">LeetCode - 字符串专题</a></li><li class="active"><a href="/leetcode-stacks&queues.html" rel="bookmark" title="LeetCode - 栈与队列专题">LeetCode - 栈与队列专题</a></li><li><a href="/leetcode-binarytree.html" rel="bookmark" title="LeetCode - 二叉树专题">LeetCode - 二叉树专题</a></li><li><a href="/leetcode-traverse.html" rel="bookmark" title="LeetCode - 回溯专题">LeetCode - 回溯专题</a></li><li><a href="/leetcode-greedy.html" rel="bookmark" title="LeetCode - 贪心专题">LeetCode - 贪心专题</a></li><li><a href="/leetcode-dynamicprogramming.html" rel="bookmark" title="LeetCode - 动态规划专题">LeetCode - 动态规划专题</a></li><li><a href="/leetcode-doublepointer.html" rel="bookmark" title="LeetCode - 双指针专题">LeetCode - 双指针专题</a></li><li><a href="/leetcode-monotonicstacks.html" rel="bookmark" title="LeetCode - 单调栈专题">LeetCode - 单调栈专题</a></li><li><a href="/leetcode-search.html" rel="bookmark" title="LeetCode - 搜索专题">LeetCode - 搜索专题</a></li><li><a href="/leetcode-sort.html" rel="bookmark" title="LeetCode - 排序专题">LeetCode - 排序专题</a></li><li><a href="/leetcode-input&output.html" rel="bookmark" title="常见输入输出">常见输入输出</a></li><li><a href="/leetcode-analog.html" rel="bookmark" title="LeetCode - 模拟专题">LeetCode - 模拟专题</a></li></ul></div><div class="overview panel" data-title="站点概览"><div class="author" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><img class="image" loading="lazy" decoding="async" itemprop="image" alt="Jiankychen" src="/assets/avatar.webp"><p class="name" itemprop="name">Jiankychen</p><div class="description" itemprop="description"></div></div><nav class="state"><div class="item posts"><a href="/archives/"><span class="count">51</span><span class="name">文章</span></a></div><div class="item categories"><a href="/categories/"><span class="count">8</span><span class="name">分类</span></a></div><div class="item tags"><a href="/tags/"><span class="count">20</span><span class="name">标签</span></a></div></nav><div class="social"><a target="_blank" rel="noopener" href="https://github.com/jiankychen" class="item github" title="https://github.com/jiankychen"><i class="ic i-github"></i></a><a href="mailto:[email protected]" class="item email" title="mailto:[email protected]"><i class="ic i-envelope"></i></a><a target="_blank" rel="noopener" href="https://music.163.com/#/user/home?id=447771275" class="item music" title="https://music.163.com/#/user/home?id=447771275"><i class="ic i-cloud-music"></i></a><a target="_blank" rel="noopener" href="https://www.zhihu.com/people/jiankychen" class="item zhihu" title="https://www.zhihu.com/people/jiankychen"><i class="ic i-zhihu"></i></a></div><div class="menu"><li class="item"><a href="/" rel="section"><i class="ic i-home"></i>首页</a></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>文章</a><ul class="submenu"><li class="item"><a href="/archives/" rel="section"><i class="ic i-list-alt"></i>归档</a></li><li class="item"><a href="/categories/" rel="section"><i class="ic i-th"></i>分类</a></li><li class="item"><a href="/tags/" rel="section"><i class="ic i-tags"></i>标签</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>链接</a><ul class="submenu"><li class="item"><a href="/peers/" rel="section"><i class="ic i-magic"></i>链环</a></li><li class="item"><a href="/friends/" rel="section"><i class="ic i-heart"></i>友链</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-stars"></i>关于</a><ul class="submenu"><li class="item"><a href="/owner/" rel="section"><i class="ic i-user"></i>关于博主</a></li><li class="item"><a href="/site/" rel="section"><i class="ic i-paw"></i>关于本站</a></li><li class="item"><a href="/update/" rel="section"><i class="ic i-cloud"></i>更新日志</a></li></ul></li></div></div></div></div><ul id="quick"><li class="prev pjax"><a href="/leetcode-binarytree.html" rel="prev" title="上一篇"><i class="ic i-chevron-left"></i></a></li><li class="up"><i class="ic i-arrow-up"></i></li><li class="down"><i class="ic i-arrow-down"></i></li><li class="next pjax"><a href="/KMP.html" rel="next" title="下一篇"><i class="ic i-chevron-right"></i></a></li><li class="percent"></li></ul></div></div><div class="dimmer"></div></div></main><footer id="footer"><div class="inner"><div class="widgets"><div class="rpost pjax"><h2>随机文章</h2><ul><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-greedy.html">LeetCode - 贪心专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/priority-queue.html">优先级队列</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-doublepointer.html">LeetCode - 双指针专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Python/" title="分类于Python">Python</a></div><span><a href="/python-basics.html">Python 基本语法</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-binarysearch.html">LeetCode - 二分查找专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-monotonicstacks.html">LeetCode - 单调栈专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/KMP.html">KMP 算法</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/dynamic-programming.html">动态规划</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-vectors.html">LeetCode - 数组专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Python/" title="分类于Python">Python</a></div><span><a href="/python-conda.html">conda 常用命令</a></span></li></ul></div><div class="rpost pjax"><h2>最新评论</h2><ul class="leancloud-recent-comment" id="new-comment"></ul></div></div><div class="status"><div class="copyright">© 2021 -<span itemprop="copyrightYear">2024</span><span class="with-love"><i class="ic i-sakura rotate"></i></span><span class="author" itemprop="copyrightHolder">Jiankychen @ Jiankychen</span></div><div class="count"><span class="post-meta-item-icon"><i class="ic i-chart-area"></i></span><span title="站点总字数">955k 字</span><span class="post-meta-divider"> | </span><span class="post-meta-item-icon"><i class="ic i-coffee"></i></span><span title="站点阅读时长">14:28</span></div><div class="powered-by">基于 <a target="_blank" rel="noopener" href="https://hexo.io/">Hexo</a> & Theme.<a target="_blank" rel="noopener" href="https://github.com/theme-shoka-x/hexo-theme-shokaX/">ShokaX</a></div></div><script src="https://unpkg.com/[email protected]/bsz.pure.mini.js"></script><div id="busuanzi-wrap"><span class="ic i-eye"></span><span id="busuanzi_container_site_pv">本站总访问量 <span id="busuanzi_value_site_pv"></span> 次</span> | <span class="ic i-user"></span><span id="busuanzi_container_site_uv">本站总访客量 <span id="busuanzi_value_site_uv"></span> 次</span></div></div></footer></div><script data-config="" type="text/javascript">var LOCAL = {
ispost: true,
path: `/leetcode-stacks&queues`,
favicon: {
show: `Jiankychen`,
hide: `Jiankychen`
},
search: {
placeholder: "文章搜索",
empty: "关于 「 ${query} 」，什么也没搜到",
stats: "${time} ms 内找到 ${hits} 条结果"
},
copy_tex: true,
katex: true,
mermaid: false,
audio: undefined,
fancybox: true,
nocopy: false,
outime: true,
template: `<div class="note warning"><p><span class="label warning">文章时效性提示</span><br>这是一篇发布于 {{publish}} 天前，最后一次更新在 {{updated}} 天前的文章，部分信息可能已经发生改变，请注意甄别。</p></div>`,
quiz: {
choice: `单选题`,
multiple: `多选题`,
true_false: `判断题`,
essay: `问答题`,
gap_fill: `填空题`,
mistake: `错题备注`
},
ignores: [
(uri) => uri.includes('#'),
(uri) => new RegExp(LOCAL.path + '$').test(uri),
[]
]
};
</script><script src="https://lf9-cdn-tos.bytecdntp.com/cdn/expire-6-M/pace/1.2.4/pace.min.js" async=""></script><script src="https://polyfill.io/v3/polyfill.min.js?features=default,fetch" defer=""></script><script src="/js/siteInit.js?v=0.4.2" type="module" fetchpriority="high" defer=""></script></body></html>