30天刷题挑战（二十七）

题目来源: LeetCode 75 面试经典 150 题

739. 每日温度

思路

单调栈，从数组右边开始遍历，比当前值小的就入栈，比当前值大的将它的索引放入结果数组，

代码

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function(temperatures) {
  const stack = []
  const res = Array(temperatures.length).fill(0);

  for (let i = temperatures.length - 1; i >= 0; i--) {
    while (stack.length && temperatures[i] >= temperatures[stack[stack.length - 1]]) {
      stack.pop()
    }

    if (stack.length) {
      res[i] = stack[stack.length - 1] - i
    }
    stack.push(i)
  }

  return res;
};

901. 股票价格跨度

思路

初始化一个栈和一个当前天数，在 next 方法中每次去栈顶找比当前值小的数，如果栈顶值小于当前值就出栈，将当前值和天数入栈。

代码

var StockSpanner = function() {
  this.curDay = -1
  this.stack = [[-1, Infinity]]
};

/** 
 * @param {number} price
 * @return {number}
 */
StockSpanner.prototype.next = function(price) {
  while (price >= this.stack[this.stack.length - 1][1]) {
    this.stack.pop();
  }
  this.stack.push([++this.curDay, price]);

  return this.curDay - this.stack[this.stack.length - 2][0];
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * var obj = new StockSpanner()
 * var param_1 = obj.next(price)
 */

380. O(1) 时间插入、删除和获取随机元素

思路

使用一个数组存储数据，使用一个 Map 保存数据在数组中的索引值，以到达 O(1) 的时间复杂度

代码

var RandomizedSet = function() {
    this.nums = [];
    this.indices = new Map();
};

RandomizedSet.prototype.insert = function(val) {
    if (this.indices.has(val)) {
        return false;
    }
    let index = this.nums.length;
    this.nums.push(val);
    this.indices.set(val, index);
    return true;
};

RandomizedSet.prototype.remove = function(val) {
    if (!this.indices.has(val)) {
        return false;
    }
    let id = this.indices.get(val);
    this.nums[id] = this.nums[this.nums.length - 1];
    this.indices.set(this.nums[id], id);
    this.nums.pop();
    this.indices.delete(val);
    return true;
};

RandomizedSet.prototype.getRandom = function() {
    const randomIndex = Math.floor(Math.random() * this.nums.length);
    return this.nums[randomIndex];
};

本文完，感谢阅读。