home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Maximal Rectangle ใน C++

สมมติว่าเรามีเมทริกซ์ 2D แบบไบนารีที่มีค่า 0 และ 1 เราต้องหาสี่เหลี่ยมผืนผ้าที่ใหญ่ที่สุดที่ประกอบด้วยแต่ 1 และคืนค่าพื้นที่

ขั้นตอนการแก้ปัญหา

  • กำหนดฟังก์ชัน getAns รับอาร์เรย์ a
  • สร้างสแต็ก st, i := 0, ans := 0
  • while i < ขนาดของ a
    • ถ้าสแต็กว่างหรือ a[i] >= ตัวบนสุดของสแต็ก ใส่ i ลง st, เพิ่ม i ขึ้น 1
    • อื่นๆ
      • height := a[ตัวบนสุดของสแต็ก], ลบออกจากสแต็ก
      • width := i ถ้าสแต็กว่าง มิฉะนั้น i – ตัวบนสุดของ st – 1
      • area := height * width
      • ans := max ของ ans และ area
  • while st ไม่ว่าง
    • height := a[ตัวบนสุดของ st], ลบออกจากสแต็ก
    • width := ขนาดของ a ถ้า st ว่าง มิฉะนั้น ขนาดของ a – ตัวบนสุดของ st – 1
    • area := height * width
    • ans := max ของ ans และ area
  • คืนค่า ans
  • จากเมธอดหลัก
    • ans := 0, n := ขนาดของ x
    • ถ้า n เป็นศูนย์ คืนค่า 0
    • m := ขนาดของ x[0]
    • สร้างอาร์เรย์ height ขนาด m
    • for i ในช่วง 0 ถึง n – 1
      • for j ในช่วง 0 ถึง m – 1
        • ถ้า x[i, j] = 1 เพิ่ม height[j] ขึ้น 1 มิฉะนั้น height[j] := 0
      • ans := max ของ ans และ getAns(height)
    • คืนค่า ans

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int getAns(vector<int> a){
        stack<int> st;
        int i = 0;
        int ans = 0;
        while(i < a.size()){
            if(st.empty() || a[i] >= a[st.top()]){
                st.push(i);
                i++;
            } else {
                int height = a[st.top()];
                st.pop();
                int width = st.empty() ? i : i - st.top() - 1;
                int area = height * width;
                ans = max(ans, area);
            }
        }
        while(!st.empty()){
            int height = a[st.top()];
            st.pop();
            int width = st.empty() ? a.size() : a.size() - st.top() - 1;
            int area = height * width;
            ans = max(ans, area);
        }
        return ans;
    }
    int maximalRectangle(vector<vector<char>>& x) {
        int ans = 0;
        int n = x.size();
        if(!n) return 0;
        int m = x[0].size();
        vector<int> height(m);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(x[i][j] == '1') height[j]++;
                else height[j] = 0;
            }
            ans = max(ans, getAns(height));
        }
        return ans;
    }
};

int main(){
    vector<vector<char>> v = {
        {'1','0','1','0','0'},
        {'1','0','1','1','1'},
        {'1','1','1','1','1'},
        {'1','0','0','1','0'}
    };
    Solution ob;
    cout << (ob.maximalRectangle(v));
}

อินพุต

{{'1','0','1','0','0'}, {'1','0','1','1','1'}, {'1','1','1','1','1'}, {'1','0','0','1','0'}}

เอาต์พุต

6