题目495题
提莫攻击
在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄，他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。现在，给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间，你需要输出艾希的中毒状态总时长。
你可以认为提莫在给定的时间点进行攻击，并立即使艾希处于中毒状态。
示例1:
输入: [1,4], 2
输出: 4
原因: 第 1 秒初，提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟，直到第 2 秒末结束。
第 4 秒初，提莫再次攻击艾希，使得艾希获得另外 2 秒中毒时间。
所以最终输出 4 秒。
思路
双指针
实现
class Solution {
public int findPoisonedDuration(int[] timeSeries, int duration) {
int result = 0;
int left = 0;
int right = 0;
for (int time: timeSeries){
if (time >= right){
result += duration;
left = time;
right = left + duration;
}
else{
left = time;
result = result + duration + left - right;
right = left + duration;
}
}
return result;
}
}
题目496题
下一个更大的元素I
给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
思路
单调栈：首先遍历nums2，利用哈希表记录每个元素下一个更大值。然后遍历nums1获取结果
实现
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Stack < Integer > stack = new Stack<>();
HashMap < Integer, Integer > map = new HashMap < > ();
for(int num: nums2){
while(! stack.empty() && stack.peek()<num){
map.put(stack.pop(), num);
}
stack.push(num);
}
while(!stack.empty()){
map.put(stack.pop(),-1);
}
int[] result = new int[nums1.length];
for(int i = 0; i < nums1.length; i++){
result[i] = map.get(nums1[i]);
}
return result;
}
}
题目497题
非重叠矩阵中的随机点
给定一个非重叠轴对齐矩形的列表 rects，写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。
示例 1：
输入:
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
输出:
[null,[4,1],[4,1],[3,3]]
思路
首先计算所有整数点的总和，然后采用蓄水池抽样，或者二分查找，找到随机点。
实现
import java.util.Random;
class Solution {
private int[][] rects;
private int rectsNum = 0;
private List<Integer> rectArray = new ArrayList<>();
public Solution(int[][] rects) {
this.rects = rects;
for (int[] rect: rects){
rectsNum += (rect[2] - rect[0] + 1)*(rect[3] - rect[1] + 1);
rectArray.add(rectsNum);
}
}
public int[] pick() {
Random random =new Random();
int randomIndex = random.nextInt(rectsNum);
int left = 0;
int right = rects.length-1;
while(left != right){
int mid = left + (right-left)/2;
if(randomIndex >= rectArray.get(mid)){
left = mid +1;
}
else{
right = mid;
}
}
int rectsIndex = left;
int[] rect = rects[rectsIndex];
int length = rect[2] - rect[0] + 1;
int high = rect[3] - rect[1] + 1;
int lengthIndex = random.nextInt(length);
int highIndex = random.nextInt(high);
int[] result = new int[2];
result[0] = rect[0] + lengthIndex;
result[1] = rect[1] + highIndex;
return result;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(rects);
* int[] param_1 = obj.pick();
*/