155. 最小栈
题目链接：155. 最小栈
难度：中等
刷题状态：1刷
新知识：
解题过程
思考
示例 1:
输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2] 解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2. 用this.items表示数组
题解分析
参考题解链接：最小栈 （辅助栈法，清晰图解）
手搓答案（无非废话版）
var MinStack = function() {
this.items=[]
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function(val) {
this.items.push(val)
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
this.items.pop()
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.items[this.items.length-1]
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return Math.min(...this.items)
};
/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(val)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/总结
定义各种方法用MinStack.prototype.
394. 字符串解码
题目链接：394. 字符串解码
难度：中等
刷题状态：1刷
新知识：
解题过程
思考
示例 1：
输入：s = "3[a]2[bc]" 输出："aaabcbc"
题解分析
参考题解链接：字符串解码（辅助栈法 / 递归法，清晰图解）
详细分析如下
/**
* @param {string} s
* @return {string}
*/
var decodeString = function(s) {
let arr=[],res='',sum=0
for(let c of s){
if(c=='['){
arr.push([sum,res])
res='',sum=0
}else if(c==']'){
//顶层弹出上一组数据
let [curSum,lastRes]=arr.pop()
res=lastRes+res.repeat(curSum)
}else if(c>='0'&&c<='9'){
sum+=sum*10+parseInt(c,10)
}else{
res+=c
}
}
return res
};手搓答案（无非废话版）
/**
* @param {string} s
* @return {string}
*/
var decodeString = function(s) {
let res='',arr=[],sum=0
for(let c of s){
if(c>='0'&&c<='9'){
sum=sum*10+parseInt(c,10)
}else if(c=='['){
arr.push([res,sum])
res='',sum=0
}else if(c==']'){
let [lastRes,curSum]=arr.pop()
res=lastRes+res.repeat(curSum)
}else{
res+=c
}
}
return res
};总结
注意sum的计算方法，0也包含在里面
739. 每日温度
题目链接：739. 每日温度
难度：中等
刷题状态：1刷
新知识：
解题过程
思考
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
用嵌套循环能做出来但会超时，看答案
题解分析
参考题解链接：LeetCode 图解 | 739.每日温度
详细分析如下
/**
* @param {number[]} temperatures
* @return {number[]}
*/
var dailyTemperatures = function(temperatures) {
let n=temperatures.length
let res=Array(n).fill(0)
let arr=[]
for(let i=0;i<n;i++){
let c=temperatures[i]
while(arr.length>0&&c>temperatures[arr[arr.length-1]]){
//arr存在
//比较当前遍历到的温度c 与栈顶索引对应的温度。
//如果当前温度高于栈顶索引对应的温度，就意味着找到了栈顶索引对应的那一天之后更高温度的天数。
let t=arr.pop()
res[t]=i-t
}
arr.push(i)
}
return res
};手搓答案（无非废话版）
/**
* @param {number[]} temperatures
* @return {number[]}
*/
var dailyTemperatures=function(temperatures){
let n=temperatures.length
let res=Array(n).fill(0),arr=[]
for(let i=0;i<n;i++){
let c=temperatures[i]
while(arr.length&&c>temperatures[arr[arr.length-1]]){
let t=arr.pop()
res[t]=i-t
}
arr.push(i)
}
return res
}总结
注意res[t]=i-t，这里计算的是第t天的天数差，同一个i可能对应好几个t
84. 柱状图中最大的矩形
题目链接：84. 柱状图中最大的矩形
难度：困难
刷题状态：1刷
新知识：
解题过程
思考
示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
没思路，看答案
题解分析
参考题解链接：暴力解法、栈（单调栈、哨兵技巧）
详细分析如下
/**
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea = function(heights) {
let n=heights.length
let res=0,arr=[]
for(let i=0;i<n;i++){
let c=heights[i]
// 当栈不为空且当前高度小于栈顶索引对应的高度时
while(arr.length&&c<heights[arr[arr.length-1]]){
let curHeight=heights[arr.pop()]
// 弹出所有与当前高度相同的栈顶元素，以避免重复计算
while(arr.length&&curHeight==heights[arr[arr.length-1]]){
arr.pop()
}
let curWidth=arr.length?i-arr[arr.length-1]-1:i
res=Math.max(res,curHeight*curWidth)
}
arr.push(i)
}
// 处理栈中剩余的元素
while(arr.length){
let curHeight=heights[arr.pop()]
// 弹出所有与当前高度相同的栈顶元素，以避免重复计算
while(arr.length&&curHeight==heights[arr[arr.length-1]]){
arr.pop()
}
let curWidth=arr.length?n-arr[arr.length-1]-1:n
res=Math.max(res,curHeight*curWidth)
}
return res
};手搓答案（无非废话版）
/**
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea=function(heights){
let n=heights.length
let res=0,arr=[]
for(let i=0;i<n;i++){
let c=heights[i]
while(arr.length&&c<heights[arr[arr.length-1]]){
let curHeight=heights[arr.pop()]
while(arr.length&&curHeight==heights[arr[arr.length-1]]){
arr.pop()
}
let curWidth=arr.length?i-arr[arr.length-1]-1:i
res=Math.max(res,curHeight*curWidth)
}
arr.push(i)
}
while(arr.length){
let curHeight=heights[arr.pop()]
while(curHeight==heights[arr[arr.length-1]]){
arr.pop()
}
let curWidth=arr.length?n-arr[arr.length-1]-1:n
res=Math.max(res,curHeight*curWidth)
}
return res
}总结
不好理解，多看看题解链接，然后console出来看看数据
215. 数组中的第K个最大元素
题目链接：215. 数组中的第K个最大元素
难度：中等
刷题状态：1刷
新知识：
解题过程
思考
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
排序解决很简单，要用堆的方法解决问题，试试quicksort快速排序
题解分析
参考题解链接：215. 数组中的第 K 个最大元素（分治，清晰图解）
详细分析如下
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
// var findKthLargest = function(nums, k) {
// nums.sort((a,b)=>b-a)
// return nums[k-1]
// };
var findKthLargest=function(nums,k){
function quicksort(left,right){
//保存初始边界
let l=left,r=right
//选择基准值，一般是中间值
let mid=nums[Math.floor((left+right)/2)]
while(left<=right){
//降序排序
while(nums[left]>mid) left++
while(nums[right]<mid) right--
if(left<=right){
//交换元素
[nums[left],nums[right]]=[nums[right],nums[left]]
left++
right--
}
}
// console.log(nums,left,right)
//判断是否找到第k大的元素
//如果k-1在左半部分，递归左半部分
if(k-1>=l&&k-1<=right){return quicksort(l,right)}
//如果k-1在右半部分，递归右半部分
if(k-1>=left&&k-1<=r){return quicksort(left,r)}
//如果k-1刚好在分区点，返回结果
return nums[k-1]
}
return quicksort(0,nums.length-1)
}手搓答案（无非废话版）
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest=function(nums,k){
function quicksort(left,right){
let l=left,r=right
let mid=nums[Math.floor((left+right)/2)]
while(left<=right){
while(nums[left]>mid) left++
while(nums[right]<mid) right--
if(left<=right){
[nums[left],nums[right]]=[nums[right],nums[left]]
left++,right--
}
}
if(l<=k-1&&k-1<=right) return quicksort(l,right)
if(left<=k-1&&k-1<=r) return quicksort(left,r)
return nums[k-1]
}
return quicksort(0,nums.length-1)
}总结
注意let mid=nums[Math.floor((left+right)/2)]这里不能写成let mid=Math.floor((left+right)/2)，然后后面用nums[mid]，因为left，right会影响该值