算法训练营 Day 59 | ● 503.下一个更大元素II ● 42. 接雨水

[KoEkko]

503.下一个更大元素II

function nextGreaterElements(nums:number[]):number[] {
  const length = nums.length;
  const stack:number[] = [];
  stack.push(0);
  const resArr: number[] = new Array(length).fill(-1);
  for(let i = 1; i < length * 2; i++) {
    const index = i % length;
    let top = stack[stack.length - 1];
    while(stack.length && nums[top] < nums[index]) {
      resArr[top] = nums[index];
      stack.pop();
      top = stack[stack.length - 1];
    }
    if(i < length) {
      stack.push(i);
    }
  }
  return resArr;
}

42. 接雨水

function trap(height: number[]): number {
  let res = 0;
  const length = height.length;
  const stack: number[] = [];
  stack.push(0);
  for (let i = 1; i < length; i++) {
    let top = stack[stack.length - 1];
    while (stack.length && height[i] > height[top]) {
      let mid = stack.pop()!;
      if (stack.length > 0) {
        const left = stack[stack.length - 1];
        const h = Math.min(height[i], height[left]) - height[mid];
        const w = i - left - 1;
        res += h * w;
        top = stack[stack.length - 1];
      }
    }
    stack.push(i);
  }
  return res;
}