LeetCode 85. 최대 사각형
1457 단어 LeetCode
아이디어:
본 문제는 이전 문제의 변형이다. 조금만 분석해 보면 우리는 각 줄의 각 점에 대해 높이를 추출하는 것이 사실은 기둥 모양의 그림에서 가장 큰 직사각형 면적을 구하는 문제이다.leetcode 84.
구현:
우리는 매 점의 높이를 수조 dp로 기록하는데 dp의 크기는matrix[0]이다.size().그러면 본 줄의 dp는 어떻게 찾습니까?
1. 만약에 matrix[i][j]='0'이면 기둥 모양의 높이가 0이고 dp[j]=0이다.
2. 만약에'1'이면 주상도의 높이는 바로 이전 줄의 주상도 높이 +1, dp[j]=dp[j]+1이다.
그리고 줄마다 최대 사각형 면적을 구하고 마지막으로ans로 모든 줄에서 가장 큰 사각형 면적을 기록하여 되돌려주면 됩니다.
코드:
class Solution {
public:
//84 ，
int largestRectangleArea(vector& heights) {
int n=heights.size();
vector left(n),right(n,n);
stack mono_stack;
mono_stack.push(-1);
for(int i=0;i=heights[i]){
right[mono_stack.top()]=i;
mono_stack.pop();
}
left[i] = mono_stack.top();
mono_stack.push(i);
}
int ans = 0;
for(int i=0;i>& matrix) {
if(matrix.size()==0) return 0;
int n=matrix.size(),m = matrix[0].size();
int ans=0;
vector dp(m);
//
for(int i=0;i 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
