히스토그램에서 가장 큰 직사각형

문제 개요

히스토그램에서 형성할 수 있는 가장 큰 직사각형 영역을 찾는 것이 과제입니다. 히스토그램의 각 막대의 너비는 1이고 각 막대의 높이는 음수가 아닌 정수 배열로 제공됩니다.

예를 들어 높이 배열이 [2, 1, 5, 6, 2, 3]인 경우 히스토그램에서 가장 큰 직사각형 영역은 10입니다.

솔루션 접근 방식

스택 기반 접근 방식을 사용하면 문제를 효율적으로 해결할 수 있습니다. 이 접근 방식에는 히스토그램 막대의 인덱스를 추적하기 위해 스택을 유지 관리하는 작업이 포함되어 있어 선형 시간으로 최대 직사각형 영역을 계산할 수 있습니다. 알고리즘에 대한 자세한 설명은 다음과 같습니다.

1. 변수 초기화

• len: 높이 배열의 길이입니다.
• 스택: 히스토그램 막대의 인덱스를 저장하는 데 사용되는 빈 스택입니다.
• max: 지금까지 발견된 최대 직사각형 영역을 추적하는 변수입니다.
• h: 스택에서 팝되는 막대의 높이.
• w: 높이 h로 형성된 직사각형의 너비.

2. 높이 배열을 통해 반복

왼쪽에서 오른쪽으로 높이 배열을 반복하고 모든 막대가 처리되도록 배열 끝에 높이가 0인 최종 가상 막대를 추가합니다.

반복 단계:

• 현재 막대 인덱스 푸시: 각 막대에 대해 해당 인덱스를 스택에 푸시합니다. 그러나 그렇게 하기 전에 현재 막대가 스택 맨 위에 저장된 인덱스에 있는 막대보다 큰지 확인해야 합니다. 그렇지 않은 경우 스택에서 막대를 팝하여 팝된 인덱스의 막대를 가장 작은 막대(예: 직사각형의 높이)로 사용하여 형성할 수 있는 직사각형의 면적을 계산합니다.

• 스택에서 팝 및 계산 영역:

  • 스택에서 최상위 인덱스를 팝합니다. 이 인덱스는 직사각형에서 가장 작은 막대의 높이를 나타냅니다.
  • 직사각형의 너비를 계산합니다. 팝된 후 스택이 비어 있으면 팝된 막대가 지금까지 가장 작았으며 너비가 배열의 시작 부분부터 현재 인덱스까지 확장되었음을 의미합니다. 그렇지 않으면 너비는 현재 인덱스와 현재 스택 상단에 있는 인덱스 사이의 거리에서 1을 뺀 값으로 결정됩니다.
  • 높이와 너비를 사용하여 직사각형의 면적을 계산하고 이 면적이 더 큰 경우 max 변수를 업데이트합니다.

3. 스택에 남은 막대 처리

모든 막대를 반복한 후에도 스택에 일부 막대가 남아 있을 수 있습니다. 이 막대에는 오른쪽에 더 짧은 막대가 없기 때문에 처리되지 않은 높이가 있습니다. 나머지 막대도 스택에서 꺼내어 면적을 계산하여 유사하게 처리해야 합니다.

코드에 대한 자세한 설명

다음은 각 부분을 설명하는 주석이 포함된 JavaScript 코드입니다.

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
  var len = heights.length;
  var stack = [];
  var max = 0;
  var h = 0;
  var w = 0;

  // Iterate through the heights array
  for (var i = 0; i <= len; i++) {
    // Ensure the loop processes the virtual bar with height 0 at the end
    while (stack.length && (i === len || heights[i] <= heights[stack[stack.length - 1]])) {
      // Pop the top index from the stack
      h = heights[stack.pop()];
      // Calculate the width of the rectangle
      w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      // Update the maximum area found so far
      max = Math.max(max, h * w);
    }
    // Push the current index onto the stack
    stack.push(i);
  }

  return max;
};

복잡성 분석

• 시간 복잡도: O(n), 여기서 n은 히스토그램의 막대 수입니다. 각 막대는 스택에서 최대 한 번 푸시되고 팝됩니다.
• 공간 복잡도: 인덱스를 추적하는 데 사용되는 스택의 경우 O(n)

위 내용은 히스토그램에서 가장 큰 직사각형의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!