nber1994



leetcode-栈

August 9, 2019

leetcode-栈

package main

import "fmt"

func main() {
        a := &TreeNode{7, nil, nil}
        b := &TreeNode{3, nil, nil}
        c := &TreeNode{15, nil, nil}
        d := &TreeNode{9, nil, nil}
        e := &TreeNode{20, nil, nil}
        a.Left = b
        a.Right = c
        c.Left = d
        c.Right = e
        obj := Constructor(a)
        for obj.HasNext() {
                fmt.Println(obj.Next())
        }
}

type TreeNode struct {
        Val   int
        Left  *TreeNode
        Right *TreeNode
}

//实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
//
//调用 next() 将返回二叉搜索树中的下一个最小的数。
//
//BSTIterator iterator = new BSTIterator(root);
//iterator.next();    // 返回 3
//iterator.next();    // 返回 7
//iterator.hasNext(); // 返回 true
//iterator.next();    // 返回 9
//iterator.hasNext(); // 返回 true
//iterator.next();    // 返回 15
//iterator.hasNext(); // 返回 true
//iterator.next();    // 返回 20
//iterator.hasNext(); // 返回 false
//
//
//提示:
//
//next() 和 hasNext() 操作的时间复杂度是 O(1),并使用 O(h) 内存,其中 h 是树的高度。
//你可以假设 next() 调用总是有效的,也就是说,当调用 next() 时,BST 中至少存在一个下一个最小的数。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type BSTIterator struct {
        stack []*TreeNode
        size  int
}

func (this *BSTIterator) Push(v *TreeNode) {
        this.stack = append(this.stack, v)
        this.size++
}

func (this *BSTIterator) Pop() *TreeNode {
        if this.size == 0 {
                return nil
        }
        res := this.stack[this.size-1]
        this.stack = this.stack[:this.size-1]
        this.size--
        return res
}

func Constructor(root *TreeNode) BSTIterator {
        myBSTIterator := new(BSTIterator)
        myBSTIterator.stack = []*TreeNode{}
        myBSTIterator.size = 0
        for root != nil {
                myBSTIterator.Push(root)
                root = root.Left
        }
        return *myBSTIterator
}

/** @return the next smallest number */
func (this *BSTIterator) Next() int {
        res := this.Pop()
        item := res.Right
        for item != nil {
                this.Push(item)
                item = item.Left
        }
        return res.Val
}

/** @return whether we have a next smallest number */
func (this *BSTIterator) HasNext() bool {
        return this.size > 0
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */


//括号的分数
//给定一个平衡括号字符串 S,按下述规则计算该字符串的分数:
//
//() 得 1 分。
//AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。
//(A) 得 2 * A 分,其中 A 是平衡括号字符串。
//
//
//示例 1:
//
//输入: "()"
//输出: 1
//示例 2:
//
//输入: "(())"
//输出: 2
//示例 3:
//
//输入: "()()"
//输出: 2
//示例 4:
//
//输入: "(()(()))"
//输出: 6
//
//
//提示:
//
//S 是平衡括号字符串,且只含有 ( 和 ) 。
//2 <= S.length <= 50
type Stack struct {
        stack []int
        size  int
}

func (this *Stack) push(v int) {
        this.stack = append(this.stack, v)
        this.size++
}

func (this *Stack) pop() int {
        res := this.stack[this.size-1]
        this.stack = this.stack[:this.size-1]
        this.size--
        return res
}

func scoreOfParentheses(S string) int {
        st := &Stack{[]int{}, 0}
        sa := []byte(S)
        for _, v := range sa {
                if v == '(' {
                        st.push('(' - '0')
                } else {
                        pre := st.pop()
                        if pre == '('-'0' {
                                st.push(1)
                        } else {
                                tmp := []int{}
                                for next := pre; next != '('-'0'; next = st.pop() {
                                        tmp = append(tmp, next)
                                }
                                st.push(2 * arraySum(tmp))
                        }
                }
        }
        return arraySum(st.stack)
}

func arraySum(nums []int) int {
        sum := 0
        for _, v := range nums {
                if v > 0 {
                        sum += v
                }
        }
        return sum
}

//用队列实现栈
//使用队列实现栈的下列操作:
//
//push(x) -- 元素 x 入栈
//pop() -- 移除栈顶元素
//top() -- 获取栈顶元素
//empty() -- 返回栈是否为空
//注意:
//
//你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
//你所使用的语言也许不支持队列。 你可以使用 list 或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
//你可以假设所有操作都是有效的(例如, 对一个空的栈不会调用 pop 或者 top 操作)。

type MyStack struct {
        quene1 []int
        quene2 []int
        size   int
}

/** Initialize your data structure here. */
func Constructor2() MyStack {
        return MyStack{
                []int{},
                []int{},
                0,
        }
}

/** Push element x onto stack. */
func (this *MyStack) Push(x int) {
        this.quene1 = append(this.quene1, x)
        this.size++
}

/** Removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
        for i := 0; i < this.size-1; i++ {
                this.quene2 = append(this.quene2, this.quene1[0])
                this.quene1 = this.quene1[1:]
        }
        res := this.quene1[0]
        this.quene1 = this.quene2
        this.quene2 = []int{}
        this.size--
        return res
}

/** Get the top element. */
func (this *MyStack) Top() int {
        for i := 0; i < this.size-1; i++ {
                this.quene2 = append(this.quene2, this.quene1[0])
                this.quene1 = this.quene1[1:]
        }
        res := this.quene1[0]
        this.quene2 = append(this.quene2, res)
        this.quene1 = this.quene2
        this.quene2 = []int{}
        return res
}

/** Returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
        return this.size < 1
}

/**
 * Your MyStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Empty();
 */

//用栈实现队列
//使用栈实现队列的下列操作:
//
//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 操作)。
type MyQueue struct {
        quene1 []int
        quene2 []int
        size   int
}

/** Initialize your data structure here. */
func Constructor() MyQueue {
        return MyQueue{
                []int{},
                []int{},
                0,
        }
}

/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int) {
        this.quene1 = append([]int{x}, this.quene1...)
        this.size++
}

/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
        for i := 0; i < this.size-1; i++ {
                item := this.quene1[0]
                this.quene2 = append(this.quene2, item)
                this.quene1 = this.quene1[1:]
        }
        res := this.quene1[0]
        this.quene1 = this.quene2
        this.quene2 = []int{}
        this.size--
        return res
}

/** Get the front element. */
func (this *MyQueue) Peek() int {
        for i := 0; i < this.size-1; i++ {
                item := this.quene1[0]
                this.quene2 = append(this.quene2, item)
                this.quene1 = this.quene1[1:]
        }
        res := this.quene1[0]
        this.quene2 = append(this.quene2, res)
        this.quene1 = this.quene2
        this.quene2 = []int{}
        return res
}

/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
        return this.size < 1
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Peek();
 * param_4 := obj.Empty();
 */

//柱状图中最大的柱形
//给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
//
//求在该柱状图中,能够勾勒出来的矩形的最大面积。
//
//以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]。
//
//图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。
//
//示例:
//
//输入: [2,1,5,6,2,3]
//输出: 10
func largestRectangleArea(heights []int) int {
        //每次stack中剩余的最后一个元素,可以确定它之前的都比它大,所以下标是-1
        if len(heights) == 0 || heights == nil {
                return 0
        }
        heights = append(heights, -1)
        stack := []int{}
        res := 0
        for k, v := range heights {
                if len(stack) == 0 || v >= heights[stack[len(stack)-1]] {
                        stack = append(stack, k)
                } else {
                        for len(stack) != 0 && v < heights[stack[len(stack)-1]] {
                                h := heights[stack[len(stack)-1]]
                                stack = stack[:len(stack)-1]
                                left := -1
                                if len(stack) != 0 {
                                        left = stack[len(stack)-1]
                                }
                                if res < h*(k-left-1) {
                                        res = h * (k - left - 1)
                                }
                        }
                        stack = append(stack, k)
                }
        }
        return res
}

//最大矩形
//给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。
//示例:
//输入:
//[
//  ["1","0","1","0","0"],
//  ["1","0","1","1","1"],
//  ["1","1","1","1","1"],
//  ["1","0","0","1","0"]
//]
//输出: 6
//题目难度:困难
//通过次数:3.1K
//提交次数:7.5K
//贡献者:LeetCode
//相关话题
//
//相似题目
//柱状图中最大的矩形最大正方形
func maximalRectangle(matrix1 [][]byte) int {
        if matrix1 == nil || len(matrix1) == 0 || len(matrix1[0]) == 0 {
                return 0
        }
        matrix := [][]int{}
        for k, v := range matrix1 {
                item := []int{}
                for key, val := range v {
                        item = append(item, int(val-'0'))
                        if k < 1 {
                                continue
                        }
                        if val == '1' {
                                item[key] += matrix[k-1][key]
                        }
                }
                matrix = append(matrix, item)
        }
        res := 0
        for _, v := range matrix {
                stack := []int{}
                v = append(v, -1)
                for key, val := range v {
                        if len(stack) == 0 || val >= v[stack[len(stack)-1]] {
                                stack = append(stack, key)
                        } else {
                                for len(stack) != 0 && val < v[stack[len(stack)-1]] {
                                        h := v[stack[len(stack)-1]]
                                        stack = stack[:len(stack)-1]
                                        left := -1
                                        if len(stack) != 0 {
                                                left = stack[len(stack)-1]
                                        }
                                        if res < h*(key-left-1) {
                                                res = h * (key - left - 1)
                                        }
                                }
                                stack = append(stack, key)
                        }
                }
        }
        return res
}