C++LeetCode 구현(84.직사 도 에서 가장 큰 사각형)

[LeetCode]84.Largest Rectangle in Histogram 직사 도 에서 가장 큰 사각형
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example,
Given height = [2,1,5,6,2,3],
return 10.
이 문 제 는 직사 도 에서 가장 큰 사각형 을 구하 라 고 했 는데 처음에 극치 문 제 를 보고 DP 로 해 야 한다 고 생각 했 지만 전달 식 이 생각 나 지 않 아 그만 둘 수 밖 에 없 었 다.이 문 제 는 폭력 검색 법 으로 OJ 를 통과 하지 못 할 것 이 라 고 예측 하면 좋 은 최적화 방법 이 있 습 니 다.바로 배열 을 옮 겨 다 니 는 것 입 니 다.국부 적 인 피크 치 를 찾 을 때마다(현재 의 숫자 가 뒤의 숫자 보다 크 면 현재 의 숫자 는 국부 적 인 피크 치 로 간주 하고 앞의 숫자 크기 와 무관 합 니 다)모든 값 을 앞으로 옮 겨 다 니 며 공 통 된 사각형 면적 을 계산 합 니 다.매번 대비 최대 치 를 유지 합 니 다.여기 서 왜 국 지적 피크 치 를 처리 해 야 하 는 지,문제 중의 예 를 들 어 국 지적 피크 치 는 2,6,3 이다.우 리 는 이런 국 지적 피크 치 에서 만 처리 해 야 한다.왜 비 국 지적 피크 치 에서 통계 하지 않 아 도 되 는 것 일 까?이것 은 국 지적 피크 치 가 아 닌 상황 에서 뒤의 국 지적 피크 치 는 모두 포함 할 수 있 기 때문이다.예 를 들 어 1 과 5 는 국 지적 피크 치 6 이 1 과 5 보다 높 기 때문이다.모든 1 과 5 로 구 성 된 사각형 은 6 까지 구성 할 수 있 고 6 자체 의 일부분 을 더 해 더 큰 사각형 을 구성 할 수 있다.그러면 힘 들 이지 않 고 1 과 5 곳 으로 구 성 된 사각형 을 다시 통계 할 수 있다.코드 는 다음 과 같 습 니 다:
해법 1: 

// Pruning optimize
class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int res = 0;
        for (int i = 0; i < height.size(); ++i) {
            if (i + 1 < height.size() && height[i] <= height[i + 1]) {
                continue;
            }
            int minH = height[i];
            for (int j = i; j >= 0; --j) {
                minH = min(minH, height[j]);
                int area = minH * (i - j + 1);
                res = max(res, area);
            }
        }
        return res;
    }
};

그 후에 인터넷 에서 비교적 유행 하 는 해법 을 발 견 했 습 니 다.스 택 을 이용 하여 풀 고 다른 문 서 를 참고 할 수 있 습 니 다.그러나 자세히 연 구 를 통 해 그 핵심 사상 은 위 에 있 는 가 지 를 자 르 는 방법 과 다른 점 이 있 습 니 다.여 기 는 스 택 을 유지 하고 증가 하 는 서열 을 보존 하 는 것 은 위 에 있 는 방법 으로 국부 적 인 피크 치 를 찾 는 것 과 같 습 니 다.직사 도 사각형 의 면적 이 가장 크 려 면 가능 한 한 연속 적 인 사각형 이 많 고 가장 낮은 높이 가 높 아야 한 다 는 것 을 알 수 있다.약간 나무통 원리 처럼 항상 가장 낮은 판자 가 통 의 수량 을 결정 한다.그렇다면 단조 로 운 스 택 으로 해 야 하 는 만큼 스 택 을 늘 리 는 지,아니면 스 택 을 줄 이 는 지 먼저 고려 해 야 한다.우 리 는 스 택 을 늘 리 는 것 은 점점 증가 하 는 순 서 를 유지 하 는 것 이 라 고 생각 합 니 다.스 택 보다 작은 요소 의 수 를 만나면 처 리 를 시작 합 니 다.스 택 을 줄 이 는 것 은 정반 대 입 니 다.스 택 을 유지 하 는 순 서 는 스 택 보다 큰 요소 의 수 를 만나면 처 리 를 시작 합 니 다.그러면 이 문제 의 특징 에 따라 우 리 는 높 은 판자 부터 낮은 판자 까지 순서대로 처리 해 야 한다.먼저 가장 높 은 판 자 를 처리 하고 너 비 는 1 인 다음 에 옆 에 작은 판 자 를 처리 해 야 한다.이때 길 이 는 2 이다.예전 의 높 은 판 자 는 낮은 판자 의 사각형 을 구성 할 수 있 기 때문에 우 리 는 점점 늘 어 나 는 창고 가 필요 하 다.큰 숫자 를 만나면 바로 창고 에 들 어가 야 한다.그리고 스 택 꼭대기 요소 보다 작은 숫자 를 만 났 을 때 스 택 꼭대기 요 소 를 꺼 내 처리 해 야 합 니 다.그 추출 순 서 는 높 은 판 에서 낮은 판 까지 입 니 다.그래서 만 나 는 작은 숫자 는 하나의 트리거 일 뿐 이 고 지금 은 사각형 면적 을 계산 해 야 한 다 는 뜻 입 니 다.마지막 판 자 를 처리 하기 위해 작은 trick 를 사 용 했 습 니 다.고도 배열 의 맨 뒤에 0 을 더 하면 원래 의 마지막 판 도 처리 할 수 있다.스 택 꼭대기 요 소 는 사각형 의 높이 이기 때문에 관건 은 너비 를 구 하 는 것 입 니 다.그러면 이전 과 같 습 니 다.  Trapping Rain Water  마찬가지 로 단조 로 운 창고 에 높이 를 놓 을 수 없고 좌 표를 놓 아야 한다.우리 가 먼저 창고 에서 가장 높 은 판 자 를 꺼 내 면 길이 가 1 인 사각형 면적 을 계산 한 다음 에 다음 판 자 를 꺼 낼 수 있 습 니 다.이때 낮은 판자 의 높이 에 따라 길이 가 2 인 사각형 면적 을 계산 할 수 있 습 니 다.이런 식 으로 유추 하면 숫자 가 창고 꼭대기 요소 보다 크다 는 것 을 알 고 다시 창고 에 들 어가 교묘 하 게 비교 할 수 있 습 니 다!단조 로 운 창고 문제 에 관 해 서 는 블 로 거들 의 총결산 첩 을 참고 할 수 있다.  LeetCode Monotonous Stack Summary 단조 로 운 스 택 소결코드 는 다음 과 같 습 니 다.
해법 2: 

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int res = 0;
        stack<int> st;
        height.push_back(0);
        for (int i = 0; i < height.size(); ++i) {
            if (st.empty() || height[st.top()] < height[i]) {
                st.push(i);
            } else {
                int cur = st.top(); st.pop();
                res = max(res, height[cur] * (st.empty() ? i : (i - st.top() - 1)));
                --i;
            }     
        }
        return res;
    }
};

우 리 는 위의 방법 을 약간 수정 하여 더욱 간결 하 게 할 수 있다.
해법 3:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int res = 0;
        stack<int> st;
        heights.push_back(0);
        for (int i = 0; i < heights.size(); ++i) {
            while (!st.empty() && heights[st.top()] >= heights[i]) {
                int cur = st.top(); st.pop();
                res = max(res, heights[cur] * (st.empty() ? i : (i - st.top() - 1)));
            }
            st.push(i);
        }
        return res;
    }
};

C++구현 LeetCode(84.직사 도 에서 가장 큰 사각형)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 직사 도 에서 가장 큰 사각형 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!