853. Car Fleet☆

function carFleet(target: number, position: number[], speed: number[]): number {
  const n = position.length;
  // Pair up and sort by starting position, closest to target first
  const cars = position
    .map((pos, i) => ({ pos, spd: speed[i] }))
    .sort((a, b) => b.pos - a.pos);

  // stack holds the arrival times of fleets (monotone increasing from front to back)
  const stack: number[] = [];

  for (const { pos, spd } of cars) {
    const time = (target - pos) / spd;
    // If this car arrives no later than the fleet in front, it gets blocked and joins it
    if (stack.length > 0 && time <= stack[stack.length - 1]) continue;
    // Otherwise it outruns the fleet ahead and forms a new one
    stack.push(time);
  }

  return stack.length;
}

function evalRPN(tokens: string[]): number {
  const stack: number[] = [];

  for (const tok of tokens) {
    if (tok === '+' || tok === '-' || tok === '*' || tok === '/') {
      const b = stack.pop()!;   // second operand (pushed last)
      const a = stack.pop()!;   // first operand (pushed first)
      if (tok === '+') stack.push(a + b);
      else if (tok === '-') stack.push(a - b);
      else if (tok === '*') stack.push(a * b);
      else stack.push(Math.trunc(a / b));   // truncate toward zero
    } else {
      stack.push(parseInt(tok, 10));
    }
  }

  return stack[0];
}

function calculate(s: string): number {
  let result = 0;        // running total of the current level
  let sign = 1;          // +1 or -1 applied to the next number
  let num = 0;           // the integer currently being built
  const stack: number[] = []; // saved (result, sign) pairs

  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      num = num * 10 + (ch.charCodeAt(0) - 48); // build multi-digit
    } else if (ch === '+') {
      result += sign * num;  // commit the pending number
      num = 0;
      sign = 1;
    } else if (ch === '-') {
      result += sign * num;
      num = 0;
      sign = -1;
    } else if (ch === '(') {
      stack.push(result);    // save the outer total...
      stack.push(sign);      // ...and the sign in front of '('
      result = 0;            // start a fresh sub-expression
      sign = 1;
    } else if (ch === ')') {
      result += sign * num;          // commit last number inside ()
      num = 0;
      result *= stack.pop()!;        // apply the saved sign
      result += stack.pop()!;        // add back the outer total
    }
    // spaces fall through and are ignored
  }
  return result + sign * num;        // commit any trailing number
}

function maximalRectangle(matrix: string[][]): number {
  if (matrix.length === 0 || matrix[0].length === 0) return 0;
  const cols = matrix[0].length;

  // heights[j] = run of consecutive '1's in column j, ending at the current row.
  const heights: number[] = new Array(cols).fill(0);
  let maxArea = 0;

  for (const row of matrix) {
    // 1) Update the histogram for this row.
    for (let j = 0; j < cols; j++) {
      heights[j] = row[j] === '1' ? heights[j] + 1 : 0; // '0' resets the run
    }
    // 2) Largest Rectangle in Histogram on the current heights (LC 84).
    maxArea = Math.max(maxArea, largestRectangleArea(heights));
  }

  return maxArea;
}

// Monotonic increasing stack of [startIndex, height] pairs — exactly LC 84.
function largestRectangleArea(heights: number[]): number {
  const stack: [number, number][] = [];
  let maxArea = 0;

  for (let i = 0; i <= heights.length; i++) {
    const curH = i < heights.length ? heights[i] : 0; // sentinel 0 flushes all
    let start = i;
    while (stack.length > 0 && stack[stack.length - 1][1] >= curH) {
      const [idx, h] = stack.pop()!;
      maxArea = Math.max(maxArea, h * (i - idx)); // width = i - idx
      start = idx; // inherit the popped bar's left boundary
    }
    stack.push([start, curH]);
  }

  return maxArea;
}