单调栈应用--视野总和 go版本

1.视野总和
描叙：有n个人站队，所有的人全部向右看，个子高的可以看到个子低的发型，给出每个人的身高，问所有人能看到其他人发现总和是多少。
输入：4 3 7 1
输出：2
解释：个子为4的可以看到个子为3的发型，个子为7可以看到个子为1的身高，所以1+1=2
思路：观察题之后，我们发现实际上题目转化为找当前数字向右查找的第一个大于他的数字之间有多少个数字，然后将每个结果累计就是答案，但是这里时间复杂度为O(N^2)，所以我们使用单调栈来解决这个问题。

1.设置一个单调递增的栈（栈内0~n为单调递减）
2.当遇到大于栈顶的元素，开始更新之前不高于当前人所能看到的值

详细分析参考: https://blog.csdn.net/lucky52529/article/details/89155694

func fieldSum(a []int) int {

    sum := 0

    var stack []int

    // 这里可以理解为需要一个无限高的人挡住栈中的人，不然栈中元素最后无法完全出栈

    a = append(a, math.MaxInt64)

    for i := 0; i< len(a); i++{

        if len(stack) == 0 || a[i] < a[stack[len(stack)-1]] {

            // index入栈

            stack = append(stack, i)

        } else {

            for len(stack) > 0 && a[i] >= a[stack[len(stack)-1]] {

                top :=  stack[len(stack)-1]

                // 出栈

                stack = stack[0: len(stack) - 1]

                sum += i - top - 1

            }

            stack = append(stack, i)

        }

    }

    return sum

}

根据补码，其最大值二进制表示，首位0，其余1

 

According to complement, its maximum binary representation, the first 0, the remaining 1

 

 

 

 

单调栈应用--视野总和 go版本的相关教程结束。