---
# System prepended metadata

title: 1966. Binary Searchable Numbers in an Unsorted Array
tags: [Leetcode, Monotonic Stack, Medium]

---

# 1966. Binary Searchable Numbers in an Unsorted Array
###### tags: `Leetcode` `Medium` `Monotonic Stack`
Link: https://leetcode.com/problems/binary-searchable-numbers-in-an-unsorted-array/
## 思路 $O(N)$ $O(N)$
如果当前值比前面的任何值小的话，从前面那个比它大的值到当前值，都要被清掉
**find next smaller问题**
单调递增栈
但问题是要记下之前出现的最大值 如果现在的值比当前的最大值小也不能出现在栈里 (例如[-1,5,2], 2不能被放进去)(也有可能之前的最大值已经被pop掉了，例如[-1,5,2,3], 2,3都不能被放进去)
因为最后要用栈的size作为答案
## Code
```java=
class Solution {
    public int binarySearchableNumbers(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int max = Integer.MIN_VALUE;
        for(int num:nums){
            while(!stack.isEmpty() && stack.peek()>num){
                stack.pop();
            }
            if(num > max){
                max = num;
                stack.push(num);
            }
        }
        return stack.size();
    }
}
```