[java] binary search + dynamic programming
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nbinary search + dp\nO(nlogn)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\no(n)\n\n# Code\n```\nclass Solution {\n    public int minCapability(int[] nums, int k) {\n        //binary search\n        int start = 1;\n        int end = (int)(Math.pow(10,9));\n        while(start + 1 < end){\n            int mid = start + (end - start)/2;\n            if(canRob(nums,mid,k)){\n                end = mid;\n            }\n            else{\n                start = mid;\n            }\n        }\n        if(canRob(nums,start,k)){\n            return start;\n        }else{\n            return end;\n        }\n        \n    }\n    public boolean canRob(int[] nums, int maxCapacity, int k){\n        // the number of houses robbed if start from the ith to the nth\n        int[] dp = new int[nums.length + 2];\n        for(int i = nums.length - 1 ; i >= 0; i--){\n            //base case\n            //dp[n] = 0;\n            //if the ith is over capacity, can not rob\n            if(nums[i] > maxCapacity){\n                dp[i] = dp[i + 1];\n            }\n            else{\n                dp[i] = Math.max(dp[i + 2] + 1, dp[i + 1]); \n            }\n            \n            \n        }\n        return dp[0] >= k;\n    }\n    // private boolean canRob(int[] nums, int maxMoney, int k) {\n    //     int houseStolen = 0, lastStolenIdx = -2;\n    //     for (int i = 0; i < nums.length; i++) {\n    //         if (nums[i] > maxMoney) {\n    //             continue;\n    //         }\n    //         if (i == lastStolenIdx + 1) {\n    //             continue;\n    //         }\n            \n    //         houseStolen++;    \n    //         lastStolenIdx = i; \n    //     }\n        \n    //     return houseStolen >= k;\n    // }\n}\n```
['Java']