题目描述：给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 注意空字符串可被认为是有效字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

const strKey = new Map();
strKey.set("{", "}");
strKey.set("[", "]");
strKey.set("(", ")");

// 左括号集合
const left = ['{', '[', '(']


const isValid = function (str) {
  // 空字符串无条件判断为 true
  if (!str) return true;

  // 模拟栈
  const stack = [];

  const len = str.length;
  for (let i = 0; i < len; i++) {
    const item = str[i];

    // 如果是左括号，那把对应的右括号放进栈里面
    if (left.indexOf(item) > -1) {
      stack.push(strKey.get(item));
    } else {
      // 由于栈的后进先出原则，题中`左括号必须以正确的顺序闭合`,
      // 当item为右括号时，应该和栈顶的右括号相等，否则括号的闭合规则错误返回false
      // 如果栈里面已经没有数据了,字符串还没结束，直接 闭合规则 不成立，返回false
      if (!stack.length || stack.pop() !== item) {
        return false;
      }
    }
  }
  // 校验结束，栈应该是空的
  return !stack.length
}


const str1 = "{}[]()";
const str2 = "{[()]}";
const str3 = "{}{}{()";
const str4 = "{[()]}}}";
const str5 = "{[)()]}";

console.log(isValid(str1)) // true
console.log(isValid(str2)) // true
console.log(isValid(str3)) // false
console.log(isValid(str4)) // false
console.log(isValid(str5)) // false

题目描述: 根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

  • 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

  • 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const temp = [73, 74, 75, 71, 69, 72, 76, 73];

const dailyTemperatures = function (arr) {

  const len = arr.length;
  let resArr = (new Array(len)).fill(0); // 结果数组，和温度数组等长，先占位为0
  let stack = []; // 初始化栈

  for (var i = 0; i < len; i++) {
    const item = arr[i];

    // 对比 下一个值是否大于当前值
    while (stack.length && item > arr[stack[stack.length - 1]]) {
      // 则找到了下一个比当前值大的数据，取出栈顶的数据
      let top = stack.pop();
      // 两个index 相减，算出过了几天温度超过
      resArr[top] = i - top
    }

    stack.push(i) // 像栈里push当前数据的index
  }

  return resArr

}

console.log(dailyTemperatures(temp))

题目描述：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

栈的设计——“最小栈”问题

  • push(x) —— 将元素 x 推入栈中。

  • pop() —— 删除栈顶的元素。

  • getTop() —— 获取栈顶元素。

  • getMin() —— 检索栈中的最小元素。

  • 最小栈思路：

  • 创建一个递减栈！在操作栈push,pop时，这个栈的栈顶永远保持最小数据，这样取最小值只需要取一下这个栈的栈顶，跟循环栈然后找到最小值比，是空间换时间，O(n) -> O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

function MinStack() {
  // 初始化栈
  this.stack = [];
  // 递减栈
  this.minStack = [];
}

MinStack.prototype = {
  constructor: MinStack,

  /**
   * 入栈
   * @param {*} data  入栈数据
   */
  push: function (data) {
    if (data === null || data === undefined) return;
    this.stack.push(data);
    // 当栈还是空和push的数据小于等于 minStack栈顶的值，就把这个更小的值push入minStack
    // 比栈顶还大的数据，就肯定不是最小值，不用入minStack栈
    if (!this.minStack.length || this.minStack[this.minStack.length - 1] >= data) {
      this.minStack.push(data)
    }
  },

  /**
   * 出栈
   */
  pop: function () {
    if (!this.stack.length) return null;
    // 如果出栈的值等于最小栈顶的值，证明最小值出栈了，则minStack也需要把这个最小值出栈，确保栈最小值的正确性
    if (this.stack.pop() === this.minStack[this.minStack.length - 1]) {
      this.minStack.pop()
    }
  },

  /**
   * 取栈顶的数据
   */
  getTop: function () {
    if (!this.stack.length) return null
    return this.stack[this.stack.length - 1];
  },

  /**
   * 获取栈中最小值
   */
  getMin: function () {
    if (!this.minStack.length) return null;
    return this.minStack[this.minStack.length - 1]
  }

}

const Stack = new MinStack();
Stack.push(0)
Stack.push(1)
Stack.push(-1)
Stack.push(-3)
Stack.push(1)
Stack.push(7)
Stack.pop()
Stack.push(6)


console.log(Stack.stack)    // [ 0, 1, -1, -3, 1, 6 ]
console.log(Stack.minStack) // [ 0, -1, -3 ]
console.log(Stack.getMin()) // -3
console.log(Stack.getTop()) // 6

题目描述：使用栈实现队列的下列操作：

  • push(x) – 将一个元素放入队列的尾部。
  • pop() – 从队列首部移除元素。
  • peek() – 返回队列首部的元素。
  • empty() – 返回队列是否为空。

示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false

说明:
你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

// 思路: 栈：先进后出 ，队列：先进先出，

function MyQueue() {
  this.stack1 = [];
  this.stack2 = [];
}

/**
 *  入队列
 */
MyQueue.prototype.push = function (x) {
  this.stack1.push(x)
}

/**
 *  出队列
 */
MyQueue.prototype.pop = function () {
  // 如果stack2为空，则把stack1出栈到stack2，达到翻转stack1的目的，这样由stack1入栈，stack2 出栈，实现了队列的先进先出；
  if (!this.stack2.length && this.stack1.length) {
    // 当 stack1 不为空时，出栈
    while (this.stack1.length) {
      // 将 stack1 出栈的元素推入 stack2
      this.stack2.push(this.stack1.pop())
    }
  }
  // stack2 出栈
  return this.stack2.pop()
}

/**
 * 返回队列首部的元素，跟pop比peek并没有将数据出栈
 */
MyQueue.prototype.peek = function () {
  // 如果stack2是空的，需要把stack1出栈到stack2
  if (!this.stack2.length && this.stack1.length) {
    while (this.stack1.length) {
      this.stack2.push(this.stack1.pop());
    }
  }
  const len = this.stack2.length;
  return this.stack2[len - 1];
}

/**
 * 判断是否队列是否为空
 */
MyQueue.prototype.empty = function () {
  return !this.stack1.length && !this.stack2.length
}

const Queue = new MyQueue();

console.log(Queue.isEmpty()) // true
Queue.push(1)
Queue.push(2)
console.log(Queue.isEmpty()) // false
console.log(Queue.peek())    // 1
console.log(Queue.pop())     // 1
console.log(Queue.pop())     // 2
console.log(Queue.empty())   // true