Overview

We look at the buildings in order from the sea, and each time a building appears that is taller than the tallest building seen so far, the count of “visible buildings” increases. The problem asks us to count this number.

Analysis

In this problem, buildings are lined up in order from the sea side (left side), and each building is “not visible unless it is taller than all previous buildings.” In other words, whether building \(i\) is visible is determined by comparing it with \(M\), the height of the tallest building among all buildings before it, and checking whether \(H_i > M\).

Therefore, by scanning from left to right while keeping track of “the maximum height so far,” we can efficiently determine whether each building is visible.

A naive approach would be to “find the maximum value among all previous buildings for each building every time,” but this requires up to \(N\) comparisons per building, resulting in an overall time complexity of \(O(N^2)\), which is too slow for the constraint \(N \leq 2 \times 10^5\) (it would result in TLE).

Instead, by maintaining just a single variable for “the maximum height so far,” we can determine visibility for each building in constant time, solving the entire problem in \(O(N)\).

For example, given the input 5\n2 3 1 4 2: - Building 1 (height 2): It’s the first building, so it’s visible. Count becomes 1. Update max to 2. - Building 2 (height 3): 3 > 2 → visible. Count becomes 2. Update max to 3. - Building 3 (height 1): 1 ≤ 3 → not visible. - Building 4 (height 4): 4 > 3 → visible. Count becomes 3. Update max to 4. - Building 5 (height 2): 2 ≤ 4 → not visible.

As a result, the number of visible buildings is 3.

Algorithm

1. Read the number of buildings \(N\) and the list of heights for each building from the input.
2. Initialize the variable count (number of visible buildings) and max_height (maximum height so far).
3. Scan each building’s height from left to right:
   • If the current building’s height is greater than max_height, it is visible, so increment count by 1.
   • At the same time, update max_height to the current building’s height.
4. Output count at the end.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (for the input array)

Implementation Notes

• Don’t forget to update “the maximum height so far” each time.

• The first building (index 0) is always visible, so by initializing max_height to 0, it can be handled naturally.

  Source Code

n = int(input())
heights = list(map(int, input().split()))

count = 0
max_height = 0

for height in heights:
    if height > max_height:
        count += 1
        max_height = height

print(count)

This editorial was generated by qwen3-coder-480b.