thảo luận Leetcode mỗi ngày

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int trappedWater = 0;
        if (n == 0) return 0;
        left[0] = height[0];
        for (int l = 1; l < n; l++) {
            left[l] = Math.max(left[l - 1], height[l]);
        }
        right[n - 1] = height[n - 1];
        for (int r = n - 2; r >= 0; r--) {
            right[r] = Math.max(right[r + 1], height[r]);
        }
        for (int i = 0; i < n; i++) {
            int minH = Math.min(left[i], right[i]);
            trappedWater += minH - height[i];
        }
        return trappedWater;
    }
}

class Solution:
    def trap(self, height: List[int]) -> int:
        def cal(start: int, end: int, cur: int):
            result = 0
            for idx in range(start +1, end):
                result += (cur - height[idx])
            return result
        count = {}
        for idx in range(len(height)):
            value = height[idx]
            if value in count:
                count[value].append(idx)
            else:
                count[value] = [idx]
        sortkey = sorted(count.keys())
        if len(sortkey) == 1:
            return 0
        start = len(sortkey) - 1
        if len(count[sortkey[start]]) == 1:
            count[sortkey[start-1]].append(count[sortkey[start]][0])
            height[count[sortkey[start]][0]] = sortkey[start-1]
            count[sortkey[start-1]].sort()
            start = start - 1
        boundary = [count[sortkey[start]][-1], count[sortkey[start]][-1]]
        result = 0
        for idx in range(start, 0, -1):
            key = sortkey[idx]
            if count[key][0] < boundary[0]:
                result += cal(count[key][0], boundary[0], key)
                boundary[0] = count[key][0]
            if count[key][-1] > boundary[1]:
                result += cal(boundary[1], count[key][-1], key)
                boundary[1] = count[key][-1]               
        return result

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int sum = 0;
        int[] stack = new int[height.length];
        int peek = -1;
        for (int r=0;r<height.length;r++) {
            while(peek>=0 && height[r]>height[stack[peek]]){
                int m = stack[peek];
                peek--;
                if(peek<0) break;
                int l = stack[peek];
                int h = Math.min(height[r]-height[m],height[l]-height[m]);
                sum+=(r-l-1) *h;
            }
            peek++;
            stack[peek]=r;
        }
        return sum;
    }
}

public int trap(int[] height) {
        int[] left = new int[height.length];
        int[] right = new int[height.length];
        int water = 0;

        left[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            left[i] = Math.max(left[i - 1], height[i]);
        }

        right[height.length - 1] = height[height.length - 1];
        for (int i = height.length - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], height[i]);
        }

        for (int i = 0; i < height.length; i++) {
            water += Math.min(left[i], right[i]) - height[i];
        }

        return water;
    }

public class Solution
{
    public int Trap(int[] height)
    {
        var n = height.Length;
        var max_water = new int[n];
        Array.Fill(max_water, 100001);
        int max = 0;
        for(int i = 0; i < n; i++)
        {
            max = Math.Max(max, height[i]);
            max_water[i] = Math.Min(max, max_water[i]);
        }
        max = 0;
        for (int i = n-1; i >= 0; i--)
        {
            max = Math.Max(max, height[i]);
            max_water[i] = Math.Min(max, max_water[i]);
        }
        var res = 0;
        for(int i=0; i< n; i++)
        {
            res += max_water[i] - height[i];
        }
        return res;
    }
}

class Solution:
    def trap(self, height: List[int]) -> int:
        # devide the problem into smaller pieces with max_height as boundaries
        max_height = max(height)
        sections = [[]]
        i = 0
        for h in height:
            if h < max_height:
                sections[i].append(h)
            else:
                sections[i].append(h)
                sections.append([h])
                i += 1
        sections[-1] = sections[-1][::-1]
        # print(sections)
        def sector_water(nums: List):
            '''
            calculate the water stored in each section. The section must be monotone increasingly.
            '''
            ans = 0
            for idx, num in enumerate(nums):
                if idx == 0: continue
                if num < nums[idx-1]:
                    ans += nums[idx-1] - num
                    nums[idx] = nums[idx-1]
                # print(nums)
            return ans
        res = 0       
        for idx, sec in enumerate(sections):
            if idx == 0 or idx == len(sections) - 1:
                res += sector_water(sec)
            else:
                res += max_height * len(sec) - sum(sec)
        return res
[/SPOILER]

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int arr[n + 1];
        arr[0] = 0;
        arr[1] = 0;
        int m = 0;
        int s = 0;
        int f = 0;
        int area = 0;
        if (n == 1 || n == 2){
            return 0;
        }
        else{
            if (height[1] >= height[0]){
                m = 1;
            }
            for (int i = 2; i < n; i++){
                for (int j = i - 1; j >= m; j--){
                    f = j;
                    if (height[j] >= height[i] || j == m){
                        break;
                    }
                    s += height[j];
                }
                area = (min (height[f], height[i]) * (i - f - 1) - s);
                arr[i] = arr[f] + area;
                s = 0;
                area = 0;
                if (height[i] > height[m]){
                    m = i;
                }
            }
        }
        return arr[n - 1];
    }
};

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        vector<int> dp(matrix[0].size(), 0);
        int ret = 0;
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                dp[j] = matrix[i][j] == '1' ? dp[j] + 1 : 0;
            }
            ret = max(ret, largestRectangleArea(dp));
        }
        return ret;
    }
    
    int largestRectangleArea(vector<int>& heights) {
        vector<pair<int,int>> s = {{heights[0], 0}};
        int ret = 0;
        for (int i = 1; i < heights.size(); ++i) {
            int j = i;
            while (!s.empty() && heights[i] <= s.back().first) {
                auto [val, idx] = s.back();
                j = idx;
                ret = max(ret, val*(i-idx));
                s.pop_back();
            }
            s.emplace_back(heights[i], j);
        }
        while (!s.empty()) {
            auto [val, idx] = s.back();
            ret = max(ret, val*(int(heights.size())-idx));
            s.pop_back();
        }
        return ret;
    }
};

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        dp = [[0 for _ in range(n)] for _ in range(m) ]
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '0':
                    continue
                
                count = 0 if matrix[i][j] == "0" else 1
                if i == 0:
                    dp[i][j] = count
                else:
                    dp[i][j] = dp[i-1][j] + count

        ans = 0
        for i in range(m):
            nextSmaller = [n]*n
            stack = []
            for j in range(n):
                while stack and dp[i][stack[-1]] > dp[i][j]:
                    nextSmaller[stack.pop()] = j

                stack.append(j)

            previousSmaller = [-1]*n
            stack = []
            for j in range(n-1, -1, -1):
                while stack and dp[i][stack[-1]] > dp[i][j]:
                    previousSmaller[stack.pop()] = j

                stack.append(j)

            for j in range(n):
                ans = max(ans, dp[i][j]*(nextSmaller[j] - previousSmaller[j] - 1))
                    
        return ans

class Solution {
    public int maximalRectangle(char[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[][] horizontal = new int[rows + 1][cols + 1];
        int[][] vertical = new int[rows + 1][cols + 1];
        int[][] areas = new int[rows + 1][cols + 1];

        for(int r = 1; r <= rows; r++){
            for(int c = 1; c <= cols; c++){
                if(matrix[r-1][c-1] == '1')
                    horizontal[r][c] = horizontal[r][c-1] + 1;             
            }
        }

        for(int c = 1; c <= cols; c++){
            for(int r = 1; r <= rows; r++){
                if(matrix[r-1][c-1] == '1')
                    vertical[r][c] = vertical[r - 1][c] + 1;
            }
        }

        for(int r = 1; r <= rows; r++){
            for(int c = 1; c <= cols; c++){
                int minHorizontal = Integer.MAX_VALUE, i = 0, maxArea = 0;
                while(i < vertical[r][c]){
                    if(vertical[r][c] == 0)
                        break;
                    minHorizontal = Math.min(minHorizontal, horizontal[r - i][c]);
                    maxArea = Math.max(maxArea, minHorizontal * (i + 1));
                    i++;
                }
                areas[r][c] = maxArea;
            }
        }
        return findMaxIn2DArray(areas);
    }

    private int findMaxIn2DArray(int[][] matrix){
        int max = Integer.MIN_VALUE;
        for(int r = 0; r < matrix.length; r++){
            for(int c = 0; c < matrix[0].length; c++){
                max = Math.max(max, matrix[r][c]);
            }
        }
        return max;
    }
}

var maximalRectangle = function(matrix) {
    if (matrix.length === 0) return 0;
    let maxArea = 0;

    let row = matrix.length;
    let col = matrix[0].length;

    let dp = Array(row).fill().map(() => Array(col).fill(0));

    for (let i = 0; i < row; i++ ) {
        for (let j = 0; j < col; j++) {
            if (matrix[i][j] == '1') {
                dp[i][j] = j === 0 ? 1 : dp[i][j-1] + 1;
                width = dp[i][j];

                for (let k = i; k >= 0; k-- ) {
                    width = Math.min(width, dp[k][j]);
                    maxArea = Math.max(maxArea, width * (i - k + 1));
                }
            }
        }
    }

    return maxArea;
};