문제 접근

구간들을 구해서 그 구간 사이에 찰 수 있는 물의 양을 구하고, 이걸 반복해서 모두 더하는 문제다.

그렇다면, 구간의 정의를 어떻게 내릴 수 있을까?

• 구간의 시작 지점 높이를 sH라고 잡자.

• 그리고, sH 이상의 높이를 갖는 블록(이 블록의 높이를 eH라고 해보자)이 등장하면, sH부터 해당 블록까지 사이에 있던 블록들에 대해 sH와의 차이를 구하면 된다. (sH>=eH 이므로)

• 이런 조건을 만족하기 위해서는, sH는 항상 극댓값에 위치한 블록이여야 한다.

• 또한, 여기까지만 계산한다면, sH 등장 시점부터~ 더이상 sH 이상의 높이를 갖는 블록이 나오지 않는 경우도 있을 수 있다.
  이를 위해, 블록의 뒤에서부터 다시 한 번 역 방향으로 sH가 나올때까지 이 작업을 동일하게 수행해줘야 한다.

문제 풀이

사실, 어제 풀었던 문제가 스택 관련문제라서 감명을 받아 스택으로 풀어보았다. 사실 W가 500 이라서 그냥 매번 극댓값을 찾고 극댓값과 극댓값 사이를 구간으로 잡아 처리해도 가능하다.

import java.io.*;
import java.util.*;

class Main {
    static int H;
    static int W;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        int result = 0;

        st = new StringTokenizer(br.readLine());
        int[] blocks = new int[W];
        Stack<Integer> stack = new Stack<>();
        int sH = -1;
        for (int i = 0; i < W; i++) {
            int h = Integer.parseInt(st.nextToken());
            blocks[i] = h;
            if (stack.isEmpty()) {
                stack.add(h);
            } else if (sH == -1) {
                if (stack.peek() <= h) {
                    stack.pop();
                    stack.add(h);
                } else {
                    sH = stack.peek();
                    stack.add(h);
                }
            } else {
                if (h >= sH) {
                    while (!stack.isEmpty()) {
                        result += (sH - stack.pop());
                    }
                    stack.add(h);
                    sH = -1;
                } else {
                    stack.add(h);
                }
            }
        }

        if (sH != -1) {
            stack = new Stack<>();
            int reverseSH = -1;
            for (int i = W-1; i >= 0; i--) {
                int h = blocks[i];
                if (stack.isEmpty()) {
                    stack.add(h);
                } else if (reverseSH == -1) {
                    if (stack.peek() <= h) {
                        stack.pop();
                        stack.add(h);
                    } else {
                        reverseSH = stack.peek();
                        stack.add(h);
                    }
                } else {
                    if (h >= reverseSH) {
                        while (!stack.isEmpty()) {
                            result += (reverseSH - stack.pop());
                        }
                        stack.add(h);
                        reverseSH = -1;
                    } else {
                        stack.add(h);
                    }
                }

                if (h == sH) break;
            }
        }

        System.out.println(result);
    }

}