题解 | #牛群的可视高度#
牛群的可视高度
https://www.nowcoder.com/practice/942d0585a5654dbb9d5000feaa4e177e
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param cowHeights int整型一维数组 * @return int整型 */ public int visibleCows (int[] cowHeights) { // write code here Stack<Integer> stack = new Stack<>(); for (int i = cowHeights.length - 1; i >= 0; i--) { while (!stack.isEmpty() && cowHeights[i] >= stack.peek()) { stack.pop(); } stack.add(cowHeights[i]); } return stack.size(); } }
本题考察的知识点是贪心算法,所用编程语言是java.
这题我并没有理解到贪心思想,我是按照自己的想法来的,欢迎各位举出反例。我是从后往前遍历维持一个单调递减的栈,如果当前元素不小于栈顶元素,栈顶元素出栈直到整个栈都为空或者当前元素小于栈顶元素,再将当前元素入栈,如果当前元素小于栈顶元素,直接入栈,最后返回栈的大小。