给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
class Solution {
public int findKthLargest(int[] nums, int k) {
int start=0,end=nums.length-1,index = nums.length-k;
while(start < end){
int pivot = partition(nums,start,end);
if(pivot < index){
start = pivot 1;
}else if(pivot > index){
end = pivot -1;
}else{
return nums[pivot];
}
}
return nums[start];
}
private int partition(int[] nums,int start,int end){
int pivot=start,temp;
while(start <= end){
while(start <= end && nums[start] <= nums[pivot]){
start ;
}
while(start <= end && nums[end] > nums[pivot]){
end--;
}
if(start>end)break;
temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
}
temp = nums[end];
nums[end] = nums[pivot];
nums[pivot] = temp;
return end;
}
}134.加油站
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i 1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
public int canCompleteCircuit(int[] gas, int[] cost) {
int tank = 0;
for(int i = 0;i<gas.length;i ){
tank = gas[i] -cost[i];
}
if(tank < 0){
return -1;
}
int start = 0;
int accumulate = 0;
for(int i = 0;i<gas.length;i ){
int curGain = gas[i] -cost[i];
if(accumulate curGain < 0){
start = i 1;
accumulate = 0;
}else{
accumulate = curGain;
}
}
return start;
}871.最低加油次数
思路
每驶过一个加油站，记住这个加油站有多少油。不需要立即决定要不要在这个加油站加油，如果后面有油量更多的加油站显然优先选择后面的加油。
如果当前油量不够抵达下一个加油站，必须得从之前的加油站中找一个来加油，贪心选择最大油量储备的加油站就好了。
算法
定义 pq（优先队列）为一个保存了驶过加油站油量的最大堆，定义当前油量为 tank。
如果当前油量为负数（意味着当前油量不够抵达当前位置），那就必须在驶过的加油站找一个油量储备最大来加油。
如果在某个位置油量为负，且没有加油站可用了，那就不可能完成这个任务。
class Solution {
public int minRefuelStops(int target, int tank, int[][] stations) {
// pq is a maxheap of gas station capacities
PriorityQueue<Integer> pq = new PriorityQueue(Collections.reverseOrder());
int ans = 0, prev = 0;
for (int[] station: stations) {
int location = station[0];
int capacity = station[1];
tank -= location - prev;
while (!pq.isEmpty() && tank < 0) { // must refuel in past
tank = pq.poll();
ans ;
}
if (tank < 0) return -1;
pq.offer(capacity);
prev = location;
}
// Repeat body for station = (target, inf)
{
tank -= target - prev;
while (!pq.isEmpty() && tank < 0) {
tank = pq.poll();
ans ;
}
if (tank < 0) return -1;
}
return ans;
}
}
