Update Readme.md

wisdompeak · web-flow · commit 01b33b707599 · 2021-07-24T17:45:22.000-07:00
diff --git a/Stack/1944.Number-of-Visible-People-in-a-Queue/Readme.md b/Stack/1944.Number-of-Visible-People-in-a-Queue/Readme.md
@@ -2,8 +2,8 @@
 
 &#20551;&#35774;A&#24448;&#21491;&#31532;&#19968;&#20010;&#33021;&#30475;&#21040;&#30340;&#26159;B&#65292;&#37027;&#20040;B&#20043;&#21518;&#20219;&#20309;&#27604;B&#36824;&#30702;&#30340;&#30340;&#20154;A&#37117;&#30475;&#19981;&#21040;&#12290;A&#30475;&#21040;B&#20043;&#21518;&#31532;&#19968;&#20010;&#20154;&#65292;&#19968;&#23450;&#26159;```C = nextGreater[B]```&#12290;&#21516;&#29702;&#65292;A&#22312;C&#20043;&#21518;&#30340;&#19979;&#19968;&#20010;&#33021;&#30475;&#21040;&#30340;&#20154;&#21448;&#19968;&#23450;&#26159;```D = nextGreater[C]```...&#37027;&#20040;&#36825;&#20010;&#36807;&#31243;&#25345;&#32493;&#21040;&#20160;&#20040;&#26102;&#20505;&#20572;&#27490;&#21602;&#65311;&#24605;&#32771;&#21518;&#21457;&#29616;&#65292;&#19968;&#26086;&#36935;&#21040;&#27604;A&#36824;&#39640;&#30340;&#20154;&#65292;&#36825;&#20010;&#36807;&#31243;&#23601;&#20572;&#27490;&#12290;&#22240;&#20026;A&#19981;&#21487;&#33021;&#30475;&#21040;&#20219;&#20309;nextGreater[A]&#21518;&#38754;&#30340;&#20154;&#12290;
 
-&#25152;&#20197;A&#33021;&#30475;&#21040;&#30340;&#24207;&#21015;&#65292;&#26159;&#20174;A&#21491;&#36793;&#30340;&#31532;&#19968;&#20010;&#20803;&#32032;&#24320;&#22987;&#30340;&#36882;&#22686;&#24207;&#21015;BCD&#65288;&#21363;&#19981;&#20572;&#22320;nextGreater&#65289;&#65292;&#30452;&#33267;&#36935;&#21040;&#27604;A&#36824;&#39640;&#30340;&#20803;&#32032;&#65292;&#20551;&#35774;&#26159;X&#12290;
+&#25152;&#20197;A&#33021;&#30475;&#21040;&#30340;&#24207;&#21015;&#65292;&#26159;&#20174;A&#21491;&#36793;&#30340;&#31532;&#19968;&#20010;&#20803;&#32032;&#24320;&#22987;&#30340;nextGreater&#24207;&#21015;BCD...&#30452;&#33267;&#36935;&#21040;&#27604;A&#36824;&#39640;&#30340;&#20803;&#32032;&#65292;&#20551;&#35774;&#26159;X&#12290;
 
-&#36825;&#26102;&#20505;&#25105;&#20204;&#32771;&#34385;&#19968;&#19979;A&#24038;&#36793;&#30340;&#20803;&#32032;A'&#65292;&#23545;&#23427;&#32780;&#35328;&#65292;&#26080;&#35770;A&#19982;A'&#30340;&#20851;&#31995;&#22914;&#20309;&#65292;A&#19982;X&#20043;&#38388;&#30340;BCD&#37117;&#26159;&#26080;&#27861;&#34987;A'&#30475;&#21040;&#30340;&#65288;&#22240;&#20026;&#34987;A&#36974;&#20303;&#20102;&#65289;&#12290;&#36825;&#23601;&#25552;&#37266;&#25105;&#20204;&#21487;&#20197;&#23558;BCD&#37117;&#31227;&#36208;&#12290;&#20110;&#26159;&#25105;&#20204;&#24819;&#21040;&#21487;&#20197;&#36870;&#24207;&#32500;&#25252;&#19968;&#20010;&#36882;&#20943;&#30340;&#21333;&#35843;&#26632;&#12290;
+&#36825;&#26102;&#20505;&#25105;&#20204;&#19981;&#22952;&#32771;&#34385;&#19968;&#19979;A&#24038;&#36793;&#30340;&#20803;&#32032;A'&#65292;&#23545;&#23427;&#32780;&#35328;&#65292;&#26080;&#35770;A&#19982;A'&#30340;&#20851;&#31995;&#22914;&#20309;&#65292;A&#19982;X&#20043;&#38388;&#30340;BCD...&#37117;&#26159;&#26080;&#27861;&#34987;A'&#30475;&#21040;&#30340;&#65288;&#22240;&#20026;&#34987;A&#36974;&#20303;&#20102;&#65289;&#12290;&#36825;&#23601;&#25552;&#37266;&#25105;&#20204;&#21487;&#20197;&#23558;A&#19982;X&#20013;&#38388;&#30340;&#36825;&#37096;&#20998;&#37117;&#31227;&#36208;&#12290;&#20110;&#26159;&#25105;&#20204;&#24819;&#21040;&#21487;&#20197;&#36870;&#24207;&#36941;&#21382;&#25968;&#32452;&#65292;&#32500;&#25252;&#19968;&#20010;&#36882;&#20943;&#30340;&#21333;&#35843;&#26632;&#12290;
 
-&#20855;&#20307;&#20570;&#27861;&#26159;&#65306;&#22914;&#26524;&#26032;&#36827;&#26469;&#30340;&#20803;&#32032;A&#27604;&#26632;&#39030;&#20803;&#32032;&#30702;&#65292;&#37027;&#20040;&#23427;&#21482;&#33021;&#30475;&#21040;&#26632;&#39030;&#20803;&#32032;&#12290;&#22914;&#26524;&#26032;&#36827;&#26469;&#30340;&#20803;&#32032;A&#27604;&#26632;&#39030;&#20803;&#32032;&#39640;&#65292;&#37027;&#20040;&#25152;&#26377;&#27604;A&#30702;&#30340;&#33509;&#24178;&#26632;&#39030;&#20803;&#32032;&#65288;&#20174;&#24038;&#24448;&#21491;&#21576;&#36882;&#22686;&#24207;&#21015;&#65289;&#37117;&#21487;&#20197;&#34987;A&#30475;&#21040;&#12290;&#22240;&#20026;&#36825;&#20123;&#20803;&#32032;&#23545;&#20110;A&#24038;&#36793;&#30340;&#32467;&#26524;&#27809;&#26377;&#24110;&#21161;&#65292;&#25152;&#20197;&#21487;&#20197;&#37117;&#23558;&#20854;&#36864;&#26632;&#65292;&#22312;&#36864;&#26632;&#30340;&#36807;&#31243;&#20013;&#23601;&#21487;&#20197;&#35745;&#25968;&#65292;&#24471;&#21040;&#30340;&#23601;&#26159;A&#33021;&#30475;&#21040;&#30340;&#20010;&#25968;&#12290;&#27880;&#24847;&#22914;&#26524;&#36864;&#26632;&#32467;&#26463;&#21518;&#26632;&#39030;&#36824;&#23384;&#26377;&#20803;&#32032;&#65292;&#36825;&#20010;&#20803;&#32032;&#19968;&#23450;&#27604;A&#22823;&#19988;&#33021;&#34987;A&#30475;&#35265;&#65292;&#32479;&#35745;&#36824;&#35201;&#21152;1.
+&#20855;&#20307;&#20570;&#27861;&#26159;&#65306;&#22914;&#26524;&#26032;&#36827;&#26469;&#30340;&#20803;&#32032;A&#27604;&#26632;&#39030;&#20803;&#32032;&#30702;&#65292;&#37027;&#20040;&#23427;&#21482;&#33021;&#30475;&#21040;&#26632;&#39030;&#20803;&#32032;&#12290;&#22914;&#26524;&#26032;&#36827;&#26469;&#30340;&#20803;&#32032;A&#27604;&#26632;&#39030;&#20803;&#32032;&#39640;&#65292;&#37027;&#20040;&#25152;&#26377;&#27604;A&#30702;&#30340;&#33509;&#24178;&#20010;&#26632;&#39030;&#20803;&#32032;&#65288;&#20174;&#39030;&#24448;&#24213;&#21576;&#36882;&#22686;&#24207;&#21015;&#65289;&#37117;&#21487;&#20197;&#34987;A&#30475;&#21040;&#12290;&#22240;&#20026;&#36825;&#20123;&#20803;&#32032;&#23545;&#20110;A&#24038;&#36793;&#30340;&#32467;&#26524;&#27809;&#26377;&#24110;&#21161;&#65292;&#25152;&#20197;&#21487;&#20197;&#37117;&#23558;&#20854;&#36864;&#26632;&#65292;&#22312;&#36864;&#26632;&#30340;&#36807;&#31243;&#20013;&#23601;&#21487;&#20197;&#35745;&#25968;&#65292;&#24471;&#21040;&#30340;&#23601;&#26159;A&#33021;&#30475;&#21040;&#30340;&#20010;&#25968;&#12290;&#27880;&#24847;&#22914;&#26524;&#36864;&#26632;&#32467;&#26463;&#21518;&#26632;&#39030;&#36824;&#23384;&#26377;&#20803;&#32032;&#65292;&#36825;&#20010;&#20803;&#32032;&#19968;&#23450;&#27604;A&#22823;&#19988;&#33021;&#34987;A&#30475;&#35265;&#65292;&#32479;&#35745;&#36824;&#35201;&#21152;1.

-Original file line number
+Diff line change
 假设A往右第一个能看到的是B，那么B之后任何比B还矮的的人A都看不到。A看到B之后第一个人，一定是```C = nextGreater[B]```。同理，A在C之后的下一个能看到的人又一定是```D = nextGreater[C]```...那么这个过程持续到什么时候停止呢？思考后发现，一旦遇到比A还高的人，这个过程就停止。因为A不可能看到任何nextGreater[A]后面的人。
 -所以A能看到的序列，是从A右边的第一个元素开始的递增序列BCD（即不停地nextGreater），直至遇到比A还高的元素，假设是X。
 +所以A能看到的序列，是从A右边的第一个元素开始的nextGreater序列BCD...直至遇到比A还高的元素，假设是X。
 -这时候我们考虑一下A左边的元素A'，对它而言，无论A与A'的关系如何，A与X之间的BCD都是无法被A'看到的（因为被A遮住了）。这就提醒我们可以将BCD都移走。于是我们想到可以逆序维护一个递减的单调栈。
 +这时候我们不妨考虑一下A左边的元素A'，对它而言，无论A与A'的关系如何，A与X之间的BCD...都是无法被A'看到的（因为被A遮住了）。这就提醒我们可以将A与X中间的这部分都移走。于是我们想到可以逆序遍历数组，维护一个递减的单调栈。
 -具体做法是：如果新进来的元素A比栈顶元素矮，那么它只能看到栈顶元素。如果新进来的元素A比栈顶元素高，那么所有比A矮的若干栈顶元素（从左往右呈递增序列）都可以被A看到。因为这些元素对于A左边的结果没有帮助，所以可以都将其退栈，在退栈的过程中就可以计数，得到的就是A能看到的个数。注意如果退栈结束后栈顶还存有元素，这个元素一定比A大且能被A看见，统计还要加1.
 +具体做法是：如果新进来的元素A比栈顶元素矮，那么它只能看到栈顶元素。如果新进来的元素A比栈顶元素高，那么所有比A矮的若干个栈顶元素（从顶往底呈递增序列）都可以被A看到。因为这些元素对于A左边的结果没有帮助，所以可以都将其退栈，在退栈的过程中就可以计数，得到的就是A能看到的个数。注意如果退栈结束后栈顶还存有元素，这个元素一定比A大且能被A看见，统计还要加1.