Skip to content

Latest commit

 

History

History

2282.Number-of-People-That-Can-Be-Seen-in-a-Grid

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

2282.Number-of-People-That-Can-Be-Seen-in-a-Grid

此题是1944的升级版,区别在于本题允许存在相同的元素。

基本思路是一致的。我们从左往右维护一个严格单调递减的栈。如果有新元素nums[i]大于等于栈顶元素,意味着这个栈顶元素今后的视线都会被nums[i]遮住再也看不到其他。所以将栈顶元素的计数器加1之后(对应的是它能看到nums[i]),就可以将这个栈顶元素移除了。

当该退栈的元素都拿走之后,此时的栈顶元素(如果存在)必然大于nums[i],理论上需要将这个栈顶元素的计时器也加1. 但是这里有一个特例,比如3,1,1。第二个1会把第一个1弹出再入栈,但是注意3虽然大于第二个1,可它是看不到第二个1的。因此,如果新元素nums[i]如果从栈顶刚弹出了与自己相同的元素,那么它就不能再被此时栈顶的大元素的计数器所加1(虽然大于nums[i]).