면적 이 가장 큰 사각형 (단조 창고 문제)
1406 단어 알고리즘 친구 여행
분석: 모든 사각형 에 대해 우 리 는 그것 이 왼쪽 에서 오른쪽으로 각각 연장 할 수 있 는 길 이 를 구 한 다음 에 그것 의 높이 를 곱 한다. 이것 이 바로 현재 사각형 을 최저 높이 로 하면 얻 을 수 있 는 가장 큰 면적 이다.
입력 데이터 input 에 대해 서 는 각각 input [i]
1. 스 택 이 비어 있 거나 input [i] 가 input [st. top] 보다 크 면 스 택 에 들 어 갑 니 다. 그렇지 않 으 면 스 택 에 들 어 가 는 요소 보다 큰 스 택 요소 가 스 택 에서 나 옵 니 다. 스 택 이 비어 있 거나 input [i] 보다 작은 요 소 를 만 날 때 까지.
2. 각각 st. top 에서 i 사이 의 요 소 는 모두 input [st. top] 보다 크 고 모든 스 택 의 st. top 에 대해 (i - top) * input [top] 을 구 합 니 다. 즉, 모든 st. top 위치의 사각형 이 오른쪽으로 연장 할 수 있 는 최대 면적 (왼쪽 이 그것 보다 작 습 니 다) 입 니 다.
3. 마지막 스 택 의 스 택 상단 요소 에 대해 [st. top, i] 간 의 요 소 는 모두 input [i] 보다 크기 때문에 input [top] = input [i], st. push (top), 즉 input [i] 에 대해 왼쪽으로 최대 top 까지 연장 할 수 있 기 때문에 top 을 다시 스 택 에 들 어가 top 위치의 값 을 바 꿔 야 합 니 다.
import java.util.Stack;
public class Main {
public static void main(String[] arg) {
int [] input=new int[] {7,2,1,4,5,1,3,3,-1};
Stack st =new Stack();
long max=0;
long temp=0;
int top=0;
int len=input.length;
for(int i=0;i=input[st.peek()]) {
st.push(i);
}else {
while(!st.isEmpty() && input[i] 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
면적 이 가장 큰 사각형 (단조 창고 문제)제목: N 개의 사각형 이 있 고 너 비 는 모두 1 이 며 N 개의 사각형 의 높이 를 제시 합 니 다. 분석: 모든 사각형 에 대해 우 리 는 그것 이 왼쪽 에서 오른쪽으로 각각 연장 할 수 있 는 길 이 를 구...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
