/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 如果root1为空，则直接返回root2，表示第一棵树已经被完全合并到第二棵树中
        if (root1 == null) {
            return root2;
        }
        // 如果root2为空，则直接返回root1，表示第二棵树已经被完全合并到第一棵树中
        if (root2 == null) {
            return root1;
        }
        // 创建一个新的节点，其值为root1和root2的值之和，然后递归合并左右子树
        return new TreeNode( root1.val + root2.val ,
                mergeTrees(root1.left,root2.left),
                mergeTrees(root1.right,root2.right));

    }
}

class Solution {
    public int[] nextGreaterElements(int[] nums) {

    // 数组长度
        int n = nums.length;
        // 结果数组，初始化为-1，表示没有下一个更大元素
        int[] result = new int[n];
        Arrays.fill(result, -1);
        // 使用栈来辅助寻找下一个更大元素
        Stack<Integer> stack = new Stack<>();

        // 遍历数组两次，以处理环形数组的特性
        for (int i = 0; i < 2 * n; i++) {
            // 当前遍历到的元素
            int num = nums[i % n];
            // 如果栈不为空且栈顶元素小于当前元素，则栈顶元素的下一个更大元素为当前元素
            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                result[stack.pop()] = num;
            }
            // 如果当前遍历位置小于原数组长度，则将位置入栈，用于后续寻找下一个更大元素
            if (i < n) {
                stack.push(i);
            }
        }

        // 返回结果数组
        return result;
    }
}

class Solution {
    public boolean find132pattern(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }

        Stack<Integer> stack = new Stack<>();
        int third = Integer.MIN_VALUE;

        // 从后往前遍历数组
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] < third) {
                return true;
            }
            // 维护单调递减栈
            while (!stack.isEmpty() && nums[i] > stack.peek()) {
                third = stack.pop();
            }
            stack.push(nums[i]);
        }

        return false;
    }
}

class Solution {
    public boolean detectCapitalUse(String word) {
        // 如果单词为空或只有一个字符，直接返回 true
        if (word == null || word.length() <= 1) {
            return true;
        }

        // 检查是否全部大写
        if (word.equals(word.toUpperCase())) {
            return true;
        }

        // 检查是否全部小写
        if (word.equals(word.toLowerCase())) {
            return true;
        }

        // 检查是否只有首字母大写
        if (Character.isUpperCase(word.charAt(0)) && 
            word.substring(1).equals(word.substring(1).toLowerCase())) {
            return true;
        }

        // 如果都不符合，返回 false
        return false;
    }
}

class Solution {

    private int m, n, total;
    private Map<Integer, Integer> map;
    private Random rand;

    public Solution(int m, int n) {
        this.m = m;
        this.n = n;
        this.total = m * n;
        this.map = new HashMap<>();
        this.rand = new Random();
    }
    
    public int[] flip() {

        int x = rand.nextInt(total);
        total--;

        // 查找 x 是否已经映射
        int idx = map.getOrDefault(x, x);
        // 将 x 映射到总计数末尾
        map.put(x, map.getOrDefault(total, total));

        // 计算出二维矩阵的坐标
        return new int[]{idx / n, idx % n};
    }
    
    public void reset() {
        map.clear();
        total = m * n;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(m, n);
 * int[] param_1 = obj.flip();
 * obj.reset();
 */

public class Solution {

    /**
     * 计算两个地区气温变化趋势相同的最大连续天数
     *
     * @param temperatureA 地区A的气温数组
     * @param temperatureB 地区B的气温数组
     * @return 两地气温变化趋势相同的最大连续天数
     */
    public int temperatureTrend(int[] temperatureA, int[] temperatureB) {
        int maxLength = 0;     // 最大连续天数
        int currentLength = 0; // 当前连续天数

        // 遍历两个温度数组
        for (int i = 0; i < temperatureA.length - 1; i++) {
            // 计算第i天和第i+1天之间的气温变化趋势
            int trendA = getTrends(temperatureA[i], temperatureA[i + 1]);
            int trendB = getTrends(temperatureB[i], temperatureB[i + 1]);

            // 如果两个地区的气温变化趋势相同
            if (trendA == trendB) {
                currentLength++; // 当前连续天数加1
                maxLength = Math.max(maxLength, currentLength); // 更新最大连续天数
            } else {
                currentLength = 0; // 重置当前连续天数
            }
        }

        return maxLength; // 返回最大连续天数
    }

    /**
     * 计算两个温度之间的变化趋势
     *
     * @param A 第一天的气温
     * @param B 第二天的气温
     * @return 变化趋势：0表示平稳，-1表示下降，1表示上升
     */
    private int getTrends(int A, int B) {
        if (A == B) {
            return 0; // 平稳趋势
        }
        return A < B ? -1 : 1; // 上升趋势或下降趋势
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] temperatureA = {21, 18, 18, 18, 31}; // 地区A的气温数组
        int[] temperatureB = {34, 32, 16, 16, 17}; // 地区B的气温数组

        // 输出两地气温变化趋势相同的最大连续天数
        System.out.println(solution.temperatureTrend(temperatureA, temperatureB));  // 输出：2
    }
}