此题是1944的升级版,区别在于本题允许存在相同的元素。
基本思路是一致的。我们从左往右维护一个严格单调递减的栈。如果有新元素nums[i]大于等于栈顶元素,意味着这个栈顶元素今后的视线都会被nums[i]遮住再也看不到其他。所以将栈顶元素的计数器加1之后(对应的是它能看到nums[i]),就可以将这个栈顶元素移除了。
当该退栈的元素都拿走之后,此时的栈顶元素(如果存在)必然大于nums[i],理论上需要将这个栈顶元素的计时器也加1. 但是这里有一个特例,比如3,1,1
。第二个1会把第一个1弹出再入栈,但是注意3虽然大于第二个1,可它是看不到第二个1的。因此,如果新元素nums[i]如果从栈顶刚弹出了与自己相同的元素,那么它就不能再被此时栈顶的大元素的计数器所加1(虽然大于nums[i]).