Stack

Monotonic increasing stack

let fn = (arr) => {
  let stack = [];
  let ans = 0;

  for (const num of arr) {
    // for monotonic decreasing, just flip the > to <
    while (stack.length && stack[stack.length - 1] > num) {
      // do logic
      stack.pop();
    }

    stack.push(num);
  }

  return ans;
};

Examples

Remove All Adjacent Duplicates In String

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function (s) {
  const stack = [];

  for (let i = 0; i < s.length; i++) {
    let top = stack[stack.length - 1];
    if (top === s[i]) {
      stack.pop();
    } else {
      stack.push(s[i]);
    }
  }

  return stack.join("");
};

Simplify Path

var simplifyPath = function (path) {
  let stack = [];
  let word = "";

  for (const p of path) {
    if (p !== "/") {
      word += p;
    } else {
      addInstructions(stack, word);
      word = "";
    }
  }

  addInstructions(stack, word);
  return "/" + stack.join("/");
};

function addInstructions(stack, word) {
  if (word === "..") {
    stack.pop();
  } else if (word !== "" && word !== ".") {
    stack.push(word);
  }
}

Valid Parentheses

var isValid = function (s) {
  let stack = [];
  let obj = {
    "(": ")",
    "[": "]",
    "{": "}",
  };

  for (const symb of s) {
    if (obj[symb]) {
      stack.push(symb);
    } else {
      if (stack.length === 0) {
        return false;
      }
      let pop = stack.pop();
      if (obj[pop] !== symb) {
        return false;
      }
    }
  }

  return stack.length === 0;
};

Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

var dailyTemperatures = function (temperatures) {
  let stack = [];
  let finalArr = Array(temperatures.length).fill(0);

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

    stack.push(i);
  }

  return finalArr;
};

Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max

---

[1 3 -1] -3 5 3 6 7 -> 3
1 [3 -1 -3] 5 3 6 7 -> 3
1 3 [-1 -3 5] 3 6 7 -> 5
1 3 -1 [-3 5 3] 6 7 -> 5
1 3 -1 -3 [5 3 6] 7 -> 6
1 3 -1 -3 5 [3 6 7] -> 7

var maxSlidingWindow = function (nums, k) {
  let arr = [];
  let finalArr = [];

  for (let i = 0; i < nums.length; i++) {
    while (arr.length && nums[arr[arr.length - 1]] < nums[i]) {
      arr.pop();
    }

    arr.push(i);

    if (arr[0] + k === i) {
      arr.shift();
    }

    if (i >= k - 1) {
      finalArr.push(nums[arr[0]]);
    }
  }

  return finalArr;
};