#leetcode#

#leetcode#
901.股票价格跨度
class StockSpanner {
// 单调栈：存储「索引-价格」二元组，栈内价格严格单调递减（核心特性）
// 作用：快速找到当前价格左侧第一个比它大的价格的索引
Deque<int[]> stack;
// 全局索引：记录当前调用 next 方法的次数（即当前价格的位置）
int idx;

/**
* 构造函数：初始化单调栈和全局索引
* 栈的初始化策略：
* 1. 压入哨兵元素 [-1, Integer.MAX_VALUE]，避免栈空判断
* 2. 哨兵价格为无穷大，保证所有真实价格都小于它，作为最左侧的“边界”
*/
public StockSpanner() {
stack = new ArrayDeque<int[]>();
// 哨兵元素：索引-1，价格无穷大（作为所有价格的左边界）
stack.push(new int[]{-1, Integer.MAX_VALUE});
idx = -1; // 初始索引为-1，第一次调用next时先自增为0
}
public int next(int price) {
idx++; // 全局索引自增，标记当前价格的位置

// 步骤1：维护单调栈的递减特性
// 弹出栈顶所有价格 ≤ 当前价格的元素（这些元素不可能成为后续价格的左边界）
while (price >= stack.peek()[1]) {
stack.pop();
}

// 步骤2：计算跨度 = 当前索引 - 栈顶元素的索引（栈顶是左侧第一个更大的价格）
int ret = idx - stack.peek()[0];

// 步骤3：将当前「索引-价格」压入栈，作为后续价格的候选左边界
stack.push(new int[]{idx, price});

return ret;
}
}
933.最近的请求次数
class RecentCounter {
// 队列：存储最近的请求时间戳，保证队列内的时间戳都在 [t-3000, t] 范围内
// 特性：队列先进先出，适合处理“滑动时间窗口”类问题（移除过期数据，保留有效数据）
Queue<Integer> queue;

/**
* 构造函数：初始化队列（选用ArrayDeque，效率高于LinkedList）
*/
public RecentCounter() {
queue = new ArrayDeque<Integer>();
}

public int ping(int t) {
// 步骤1：将当前请求时间戳加入队列尾部
queue.offer(t);

// 步骤2：移除所有过期的时间戳（早于 t-3000 的请求）
// 队列头部是最早的请求，只需循环检查头部是否过期，直到头部有效
while (queue.peek() < t - 3000) {
queue.poll(); // 弹出过期的头部元素
}

// 步骤3：队列中剩余的元素都是 [t-3000, t] 范围内的请求，数量即为答案
return queue.size();
}
}
88.合并两个有序数组
import java.util.Arrays;

class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 步骤1：将 nums2 的元素拷贝到 nums1 的预留位置（m 开始的 n 个位置）
// i 遍历 nums2 的索引，m+i 对应 nums1 的目标位置
for (int i = 0; i != n; ++i) {
nums1[m + i] = nums2[i];
}

// 步骤2：对合并后的 nums1 整体排序，得到有序结果
// 排序后 nums1 即为两个有序数组的合并结果
Arrays.sort(nums1);
}
}
27.移除元素
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
// 左指针：初始为0，指向新数组的下一个待填充位置
int left = 0;

// 右指针：遍历整个原数组，筛选有效元素
for (int right = 0; right < n; right++) {
// 关键判断：右指针找到有效元素（≠val）
if (nums[right] != val) {
// 将有效元素覆盖到左指针位置（原地修改）
nums[left] = nums[right];
// 左指针右移，标记下一个待填充位置
left++;
}
// 若 nums[right] == val：右指针继续遍历，左指针不动（跳过无效元素）
}

// 最终 left 的值 = 新数组中有效元素的个数（左指针走过的长度）
return left;
}
}
26.删除有序数组中的重复项
class Solution {
/**
* 题目：删除有序数组中的重复项
* 题目约束：
* 1. 数组 nums 是「非递减排序」的（有序是快慢指针去重的前提）
* 2. 原地删除重复元素，使每个元素只出现一次
* 3. 返回删除后数组的新长度，且新数组前 len 个元素为去重后的有效元素
*
* 核心思路（快慢指针法）：
* 1. 慢指针 slow：标记「去重后新数组的末尾位置」（最终 slow 的值就是新数组长度）
* 2. 快指针 fast：遍历原数组，筛选出“不重复的新元素”
* 3. 逻辑：利用数组有序的特性，判断 fast 位置元素是否与前一个元素重复，
* 不重复则将其覆盖到 slow 位置，slow 右移；重复则跳过。
*
* 时间复杂度：O(n)（仅一次遍历数组，n 为数组长度）
* 空间复杂度：O(1)（原地修改，无额外空间）
*
* @param nums 非递减排序的待去重数组
* @return 去重后新数组的长度
*/
public int removeDuplicates(int[] nums) {
int n = nums.length;
// 边界条件：空数组直接返回0，无需处理
if (n == 0) {
return 0;
}

// 初始化快慢指针：
// fast=1：从第二个元素开始遍历（第一个元素必然是唯一的，无需检查）
// slow=1：新数组的第一个元素（nums[0]）已确定，slow 指向第二个待填充位置
int fast = 1, slow = 1;

// 快指针遍历整个数组，直到末尾
while (fast < n) {
// 关键判断：当前 fast 位置元素 ≠ 前一个元素 → 是新的不重复元素
// （数组有序，重复元素必然相邻，只需比较前一个即可）
if (nums[fast] != nums[fast - 1]) {
// 将不重复元素覆盖到 slow 位置（原地修改）
nums[slow] = nums[fast];
// slow 右移，标记下一个待填充位置
++slow;
}
// 若 nums[fast] == nums[fast-1]：是重复元素，仅快指针右移，慢指针不动
++fast;
}

// 最终 slow 的值 = 去重后新数组的长度（slow 走过的位置数）
return slow;
}
}
80.删除有序数组中的重复项
class Solution {
/**
* 题目：删除有序数组中的重复项 II
* 题目约束：
* 1. 数组 nums 是「非递减排序」的（有序是快慢指针去重的前提）
* 2. 原地删除重复元素，使每个元素「最多出现2次」
* 3. 返回删除后数组的新长度，且新数组前 len 个元素为符合要求的有效元素
*
* 核心思路（快慢指针法）：
* 1. 慢指针 slow：标记「符合要求的新数组的末尾位置」（最终 slow 的值就是新数组长度）
* 2. 快指针 fast：遍历原数组，筛选出“可以保留的元素”（最多重复2次）
* 3. 核心判断逻辑：利用数组有序特性，判断当前 fast 位置元素是否与 slow-2 位置元素重复
* - 若 nums[fast] != nums[slow-2] → 该元素可保留（最多重复2次）
* - 若相等 → 该元素已重复超过2次，需跳过
*
* 时间复杂度：O(n)（仅一次遍历数组，n 为数组长度）
* 空间复杂度：O(1)（原地修改，无额外空间）
*
* @param nums 非递减排序的待处理数组
* @return 处理后新数组的长度
*/
public int removeDuplicates(int[] nums) {
int n = nums.length;
// 边界条件：数组长度 ≤ 2 时，所有元素都可保留，直接返回原长度
// （因为题目要求最多保留2次，长度≤2不可能超过限制）
if (n <= 2) {
return n;
}

// 初始化快慢指针：
// fast=2：从第三个元素开始遍历（前两个元素必然符合“最多2次”要求，无需检查）
// slow=2：新数组的前两个元素（nums[0]、nums[1]）已确定，slow 指向第三个待填充位置
int slow = 2, fast = 2;

// 快指针遍历整个数组，直到末尾
while (fast < n) {
// 关键判断：当前 fast 位置元素 ≠ slow-2 位置元素 → 可保留（最多重复2次）
// 原理：
// - slow-2 是新数组中“当前待填充位置往前数第2个位置”
// - 若 nums[fast] == nums[slow-2]，说明该元素在新数组中已出现2次，再加入就超限制
// - 若不等，说明该元素在新数组中出现次数 ≤1，可加入（最多到2次）
if (nums[slow - 2] != nums[fast]) {
// 将可保留的元素覆盖到 slow 位置（原地修改）
nums[slow] = nums[fast];
// slow 右移，标记下一个待填充位置
++slow;
}
// 若 nums[slow-2] == nums[fast]：元素重复超2次，仅快指针右移，慢指针不动
++fast;
}

// 最终 slow 的值 = 处理后新数组的长度（slow 走过的位置数）
return slow;
}
}
169.多数元素
class Solution {

/**
* 辅助方法：统计数组中每个元素的出现次数
* @param nums 输入整数数组
* @return 哈希表 Map<Integer, Integer>：key 为数组中的元素，value 为该元素的出现次数
*/
private Map<Integer, Integer> countNums(int[] nums) {
// 初始化哈希表，用于存储元素-出现次数的映射
Map<Integer, Integer> counts = new HashMap<Integer, Integer>();

// 遍历数组中的每个元素，统计出现次数
for (int num : nums) {
// 若当前元素未在哈希表中，说明是第一次出现，次数设为 1
if (!counts.containsKey(num)) {
counts.put(num, 1);
} else {
// 若当前元素已存在，取出当前次数并加 1，更新哈希表
counts.put(num, counts.get(num) + 1);
}
}

// 返回统计好的元素-次数映射表
return counts;
}

/**
* 找出数组中的多数元素（出现次数 > n/2 的元素）
* @param nums 输入整数数组（题目保证存在多数元素）
* @return 多数元素
*/
public int majorityElement(int[] nums) {
// 第一步：调用辅助方法，获取每个元素的出现次数统计
Map<Integer, Integer> counts = countNums(nums);

// 用于存储出现次数最多的键值对（初始为 null）
Map.Entry<Integer, Integer> majorityEntry = null;

// 遍历哈希表的所有键值对，寻找出现次数最多的元素
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
// 条件 1：majorityEntry 为 null → 第一次遍历，直接赋值当前键值对
// 条件 2：当前元素的出现次数 > 已记录的最大次数 → 更新为当前键值对
if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
majorityEntry = entry;
}
}

// 由于题目保证存在多数元素，majorityEntry 一定不为 null，返回其对应的元素（key）
return majorityEntry.getKey();
}
}