An array is monotonic if it is either monotone increasing or monotone decreasing.
An array nums is monotone increasing if for all i <= j, nums[i] <= nums[j]. An array nums is monotone decreasing if for all i <= j, nums[i] >= nums[j].
Given an integer array nums, return true if the given array is monotonic, or false otherwise.
Example 1:
Input: nums = [1,2,2,3] Output: true
Example 2:
Input: nums = [6,5,4,4] Output: true
Example 3:
Input: nums = [1,3,2] Output: false
Constraints:
1 <= nums.length <= 105-105 <= nums[i] <= 105program monotonic_array
implicit none
integer, parameter :: n = 4
integer, dimension(n) :: nums
logical :: result
! monotonic increasing
nums = [1, 2, 2, 3]
result = monotonic_increasing(nums)
print '(A, L1)', 'Monotonic increasing: ', result
! monotonic decreasing
nums = [6, 5, 4, 4]
result = monotonic_decreasing(nums)
print '(A, L1)', 'Monotonic decreasing: ', result
! not monotonic
nums = [1, 3, 2]
result = monotonic_increasing(nums)
print '(A, L1)', 'Not monotonic: ', result
contains
function monotonic_increasing(nums) result(is_monotonic)
implicit none
integer, dimension(:), intent(in) :: nums
logical :: is_monotonic
integer :: i, j
is_monotonic = .true.
do i = 1, size(nums)-1
do j = i+1, size(nums)
if (nums(i) > nums(j)) then
is_monotonic = .false.
exit
end if
end do
if (.not. is_monotonic) exit
end do
end function monotonic_increasing
function monotonic_decreasing(nums) result(is_monotonic)
implicit none
integer, dimension(:), intent(in) :: nums
logical :: is_monotonic
integer :: i, j
is_monotonic = .true.
do i = 1, size(nums)-1
do j = i+1, size(nums)
if (nums(i) < nums(j)) then
is_monotonic = .false.
exit
end if
end do
if (.not. is_monotonic) exit
end do
end function monotonic_decreasing
end program monotonic_arraytemp.f95:19:4:
19 | nums = [1, 3, 2]
| 1
Error: Different shape for array assignment at (1) on dimension 1 (4 and 3)
```
module monotonic_array_module
implicit none
contains
function is_monotonic_array(nums) result(is_monotonic)
integer, intent(in) :: nums(:)
logical :: is_monotonic
integer :: i, j
is_monotonic = .true.
do i = 2, size(nums)
if (nums(i) < nums(i-1)) then
is_monotonic = .false.
exit
end if
end do
if (is_monotonic) then
do i = 2, size(nums)
if (nums(i) > nums(i-1)) then
is_monotonic = .false.
exit
end if
end do
end if
return
end function is_monotonic_array
end module monotonic_array_module
program main
use monotonic_array_module
implicit none
integer, parameter :: nums1(4) = [1, 2, 2, 3]
integer, parameter :: nums2(4) = [6, 5, 4, 4]
integer, parameter :: nums3(3) = [1, 3, 2]
write (*, '(A)') 'Examples:'
write (*, '(A, L1)') 'nums1: ', is_monotonic_array(nums1)
write (*, '(A, L1)') 'nums2: ', is_monotonic_array(nums2)
write (*, '(A, L1)') 'nums3: ', is_monotonic_array(nums3)
end program main
```
temp.f95:1:2:
1 | ```
| 1
Error: Invalid character in name at (1)
temp.f95:48:2:
48 | ```
| 1
Error: Invalid character in name at (1)
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def maxDepth(node):
if node is None:
return 0
else:
return max(maxDepth(node.left), maxDepth(node.right)) + 1
def subtreeWithAllDeepest(root):
if root is None:
return None
leftDepth = maxDepth(root.left)
rightDepth = maxDepth(root.right)
if leftDepth == rightDepth:
return root
if leftDepth > rightDepth:
return subtreeWithAllDeepest(root.left)
else:
return subtreeWithAllDeepest(root.right)
The algorithm works as follows:
1. Create a helper function maxDepth to find the maximum depth of a given node in the tree.
2. Create the main function subtreeWithAllDeepest that takes the root of the tree as input.
3. If the root is null, return null.
4. Calculate the maximum depth of the left and right children of the root.
5. If the maximum depths of both children are equal, return the root since the subtree with all deepest nodes is rooted at the current root.
6. If the maximum depth of the left child is greater than that of the right child, the subtree with all deepest nodes must be in the left subtree. So, call the function subtreeWithAllDeepest recursively on the left child.
7. If the maximum depth of the right child is greater than that of the left child, the subtree with all deepest nodes must be in the right subtree. So, call the function subtreeWithAllDeepest recursively on the right child.
This algorithm has a time complexity of O(n) where n is the number of nodes in the tree since it recursively traverses the entire tree in the worst case.
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v): val(v), left(NULL), right(NULL) {}
};
int maxDepth(TreeNode* node)
{
if (node == NULL)
return 0;
else
return max(maxDepth(node->left), maxDepth(node->right)) + 1;
}
TreeNode* subtreeWithAllDeepest(TreeNode* root)
{
if (root == NULL)
return NULL;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
if (leftDepth == rightDepth)
return root;
if (leftDepth > rightDepth)
return subtreeWithAllDeepest(root->left);
else
return subtreeWithAllDeepest(root->right);
}
The algorithm works as follows:
1. Create a helper function maxDepth to find the maximum depth of a given node in the tree.
2. Create the main function subtreeWithAllDeepest that takes the root of the tree as input.
3. If the root is null, return null.
4. Calculate the maximum depth of the left and right children of the root.
5. If the maximum depths of both children are equal, return the root since the subtree with all deepest nodes is rooted at the current root.
6. If the maximum depth of the left child is greater than that of the right child, the subtree with all deepest nodes must be in the left subtree. So, call the function subtreeWithAllDeepest recursively on the left child.
7. If the maximum depth of the right child is greater than that of the left child, the subtree with all deepest nodes must be in the right subtree. So, call the function subtreeWithAllDeepest recursively on the right child.
This algorithm has a time complexity of O(n) where n is the number of nodes in the tree since it recursively traverses the entire tree in the worst case.