Largest Rectangle in Histogram(Dynamic Programming)

https://leetcode.com/problems/largest-rectangle-in-histogram/description/

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

 

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

 

Constraints:

• 1 <= heights.length <= 105
• 0 <= heights[i] <= 104

아 자꾸 귀찮게 Hard 난이도를 시험에 낸다.

 

왜 그러는거야 진짜 ㅠㅠ

 

이번엔 C++로 풀어보겠다..

 

근데 풀이를 봐도 모르겄다.

#include <vector>
#include <stack>
#include <iostream>
using namespace std;

int largestRectangleAreaStack(vector<int>& heights) {
    stack<int> s; // 스택: 인덱스를 저장
    int maxArea = 0; // 최대 넓이
    int n = heights.size();

    for (int i = 0; i <= n; i++) {
        // 현재 높이를 처리 (마지막은 0으로 처리)
        int h = (i == n) ? 0 : heights[i];

        // 스택에서 높이가 현재 높이보다 큰 경우 처리
        while (!s.empty() && heights[s.top()] > h) {
            int height = heights[s.top()]; // 스택에서 막대 높이 가져오기
            s.pop(); // 스택에서 제거
            int width = s.empty() ? i : i - s.top() - 1; // 너비 계산
            maxArea = max(maxArea, height * width); // 최대 넓이 갱신
        }

        s.push(i); // 현재 인덱스를 스택에 추가
    }

    return maxArea;
}

 

다음은 DP풀이

#include <vector>
#include <iostream>
using namespace std;

int largestRectangleAreaDP(vector<int>& heights) {
    int n = heights.size();
    vector<int> left(n), right(n, n);

    // Calculate left limits
    stack<int> s;
    for (int i = 0; i < n; i++) {
        while (!s.empty() && heights[s.top()] >= heights[i]) {
            s.pop();
        }
        left[i] = s.empty() ? 0 : s.top() + 1;
        s.push(i);
    }

    // Clear the stack for right limits
    while (!s.empty()) s.pop();

    // Calculate right limits
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && heights[s.top()] >= heights[i]) {
            s.pop();
        }
        right[i] = s.empty() ? n : s.top();
        s.push(i);
    }

    // Calculate the maximum area
    int maxArea = 0;
    for (int i = 0; i < n; i++) {
        int width = right[i] - left[i];
        maxArea = max(maxArea, heights[i] * width);
    }

    return maxArea;
}

 

이건 걍 수수께끼다.

수학 못 하는 사람은 못 푸는 코딩임 ㅡ ㅡ