算法训练营 Day 57 | ● 739. 每日温度 ● 496.下一个更大元素 I

[KoEkko]

739. 每日温度

function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const res = Array(n).fill(0);
  const stack: number[] = [];
  stack.push(0);
  for (let i = 1; i < n; i++) {
    const top = temperatures[stack[stack.length - 1]];
    if (temperatures[i] < temperatures[top]) {
      stack.push(i);
    } else if (temperatures[i] === temperatures[top]) {
      stack.push(i);
    } else {
      while (
        stack.length > 0 &&
        temperatures[i] > temperatures[stack[stack.length - 1]]
      ) {
        const top = stack.pop()!;
        res[top] = i - top;
      }
      stack.push(i);
    }
  }
  return res;
}

496.下一个更大元素 I

单调栈里面存放的是要求的值；遍历nums2数组，比较栈顶元素，如果比栈顶元素大，就更新result，否则就是判断有没有存在nums1中，有的话就添加到单调栈中。

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const n = nums1.length;
  const res: number[] = Array(n).fill(-1);
  const stack: number[] = []; // 单调栈
  const map: Map<number, number> = new Map();
  nums1.forEach((value, index) => {
    map.set(value, index);
  });
  stack.push(0); // push 0 是为了可以统一逻辑，比较num[0]
  for (let i = 1; i < nums2.length; i++) {
    let top = stack[stack.length - 1];
    while (stack.length && nums2[i] > nums2[top]) {
      let index = map.get(nums2[top]);
      if (index !== undefined) { //  避免为nums2[0]不在nums1中
        res[index] = nums2[i];
      }
      stack.pop();
      top = stack[stack.length - 1];
    }
    if (map.get(nums2[i]) !== undefined) {
      stack.push(i);
    }
  }
  return res;
}