Overview

This is a problem where you count the number of mountains visible to the left from each mountain according to the given conditions, and find the total sum.

Analysis

In a naive approach, for each mountain \(i\), checking all mountains \(j\) (\(j < i\)) to its left to see if they satisfy the condition takes \(O(N^2)\) time in the worst case, which will not meet the time limit given the constraint that \(N\) can be up to \(10^6\). An efficient solution is needed.

The key observation is that the mountains visible from mountain \(i\) form a monotonically decreasing sequence of “candidates” among the mountains to its left. Specifically, on the left side of mountain \(i\), each time a taller mountain is visible, it blocks all shorter mountains behind it from being seen. This can be efficiently managed using a stack.

Algorithm

We process the mountains from left to right using a stack. For each mountain \(i\), we perform the following operations: 1. While the top of the stack is less than or equal to the current mountain’s height \(H_i\), pop those elements (since they are shorter than the current mountain and will no longer be visible from any subsequent mountains). 2. Add the size of the stack (= the number of mountains that are taller than the current mountain and satisfy the condition) to the answer. 3. Push the current mountain’s height \(H_i\) onto the stack.

With this method, the stack always maintains mountain heights in a “monotonically decreasing” order. Since each mountain is pushed onto and popped from the stack at most once, the processing is efficient.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• The stack stores mountain heights.

• The condition for popping from the stack is stack[-1] <= H[i] (note the inclusion of equality: mountains of the same height are not visible).

• By adding the stack size at each step, we obtain the number of mountains visible from the current mountain.

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    H = list(map(int, data[1:1+n]))
    
    stack = []
    total = 0
    for i in range(n):
        count = 0
        while stack and stack[-1] <= H[i]:
            stack.pop()
            count += 1
        total += len(stack)
        stack.append(H[i])
    
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.