직사 도 에서 면적 이 가장 큰 사각형 인 방 과 망 을 찾다.
1717 단어 프로 그래 밍알고리즘프로 그래 밍 언어방 과 망
제목 상세
직사 도 를 지정 합 니 다. 모든 작은 조각의 height 는 N 개의 비 마이너스 정수 에 의 해 확정 되 고 모든 작은 조각의 width 는 1 입 니 다. 직사 도 에서 면적 이 가장 큰 사각형 을 찾 으 십시오.
아래 그림 에서 보 듯 이 직사 도 에서 모든 너비 가 1 이 고 모든 주어진 높이 는 각각 [2, 1, 5, 6, 2, 3] 이다.
그러면 상기 직사 도 에서 면적 이 가장 큰 사각형 은 바로 아래 그림 에서 보 여 준 그림자 부분의 면적 이 고 면적 = 10 단위 이다.
함수 largest RectangleArea 를 완성 하여 직사 도 에서 면적 이 가장 큰 사각형 을 찾 는 기능 을 실현 하 십시오. 예 를 들 어 주어진 직사 도 각 작은 조각의 높이 = [2, 1, 5, 6, 2, 3] 를 지정 하면 10 으로 돌아 갑 니 다.
알고리즘 설명
이 문 제 는 알고리즘 이 없습니다. 첫 번 째 색인 부터 i 로 기록 하고 다른 색인 은 i 부터 오른쪽으로 이동 합 니 다. j 로 기록 하고 [i.. j] 범위 내 에서 가장 낮은 높이 를 찾 아 H 로 기록 하면 면적 은 H * (j - i + 1) 와 같 습 니 다.
옮 겨 다 니 면서 가장 큰 면적 을 찾 으 면 됩 니 다.왜 180 분 동안 문 제 를 풀 었 는 지 모 르 겠 지만 고양이 냄새 가 날 까 봐 트럼펫 으로 먼저 해 보고 큰 사이즈 로 제출 했 습 니 다.하하
include 의 헤더 파일 에 stack 이 있 는 것 을 보 았 습 니 다. 더 좋 은 알고리즘 은 스 택 을 사 용 했 을 것 입 니 다.
코드 는 다음 과 같다.
int shortest(vector<int> arr,int start,int end)
{
int shortest=arr[start];
int index=start;
int i;
if(start==end)
{
return index;
}
for(i=start;i<=end;i++)
{
if(shortest>=arr[i])
{
shortest=arr[i];
index=i;
}
}
return index;
}
int largestRectangleArea(vector<int> &height) {
//wirte your code hero
int area=0;
int max=0;
int height_index=0;
for(int i=0;i<height.size();i++)
{
for(int j=i;j<height.size();j++)
{
height_index=shortest(height,i,j);
area=(j-i+1)*(height[height_index]);
if(max < area)
max=area;
}
}
return max;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Linux Shell 프로 그래 밍 - 텍스트 처리 grep, sed사용자 가 지정 한 '모드' 에 따라 대상 텍스트 를 일치 하 게 검사 하고 일치 하 는 줄 을 인쇄 합 니 다. ##포함 되 지 않 음, 역방향 일치 \ ##키워드 앞 뒤 가 맞지 않 고 키워드 만 일치 합 니 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
