백준6549 javascript 히스토그램, 32_largestRectangularArea

 

//스택이용
const largestRectangularArea = function (histogram) {
    let len = histogram.length;
    let stack = Array.from({length: len+1}, () => 0);; //스택
    let sSize = 0; //요소의 개수
    let top = -1; //top을 가리키는 변수
    let maxArea = -1; //최대 넓이
    for(let i=0;i<len;i++) {
        //스택에 요소가 있고, 스택에 맨위에 있는 수가 i번째보다 작거나 같을동안 작동
        while(sSize>0 && histogram[stack[top]] >= histogram[i]) {
            let height = histogram[stack[top--]]; //높이는 스택의 맨위에꺼
            sSize--; //요소 하나 뺴고
            let width = sSize == 0 ? i : i-1-stack[top]; //너비는 요소가 없으면 i, 있으면 i-1-stack[top]; 
            maxArea = Math.max(maxArea, height * width); //최대 넓이
        }
        stack[++top] = i; //index값을 스택에 넣어줌
        sSize++; //요소의 개수 +1
    }
    //스택에 남아있는 값들 처리. 위에 for문안에 있는 거랑 똑같.
    while(sSize>0) {
        let height = histogram[stack[top--]];
        sSize--;
        let width = sSize == 0 ? len : len-1-stack[top];
        maxArea = Math.max(maxArea, width*height);
    }
    return maxArea;
};

 

 

코드,이론 참고 : https://st-lab.tistory.com/255